10904 2024. 04. 18 19:48:56 gortomi Rajz cpp17 Hibás válasz 0/100 101ms 29920 KiB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
int n;
int get(int v)
{
    if(v > 2 * n || v <= 0) cout << "-1" << endl;
    return p[v] == 0 ? v : p[v] = get(p[v]);
}
void unio(int a, int b)
{
    a = get(a);
    b = get(b);
    if(a > 2 * n || b > 2 * n || a == 0 || b == 0) cout << "-1" << endl;
    if(a != b)
    {
        if(r[a] < r[b]) swap(a, b);
        p[b] = a;
        if(r[a] == r[b]) r[a]++;
    }
}
struct val
{
    ll a, b, d;
};
bool insc(ll xa, ll xb, ll ya, ll yb)
{
    long double b = (yb - ya) / (xb - xa);
    if(b == 0) return 0;
    long double x = xa + (-ya / b);
    return x > 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    p.resize(2 * n + 1);
    r.resize(2 * n + 1);
    vector<ll> x(n + 1), y(n + 1);
    vector<val> e;
    for(int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
        for(int j = 1; j < i; j++)
        {
            ll dx = x[i] - x[j], dy = y[i] - y[j];
            e.push_back({j, i, dx * dx + dy * dy});
        }
    }
    sort(e.begin(), e.end(), [](val a, val b)
    {
        return a.d < b.d;
    });
    for(auto [a, b, d] : e)
    {
        bool g = insc(x[a], x[b], y[a], y[b]);
        if(g)
        {
            unio(a, b + n);
            unio(a + n, b);
        }
        else
        {
            unio(a, b);
            unio(a + n, b + n);
        }
        if(get(a) == get(a + n))
        {
            cout << d << "\n";
            return 0;
        }
    }
    cout << "-1\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Hibás válasz 3ms 2064 KiB
subtask2 0/20
3 Elfogadva 3ms 2516 KiB
4 Hibás válasz 3ms 2520 KiB
5 Futási hiba 3ms 2848 KiB
6 Hibás válasz 3ms 2788 KiB
7 Hibás válasz 3ms 2848 KiB
8 Hibás válasz 3ms 3036 KiB
9 Elfogadva 3ms 3244 KiB
10 Hibás válasz 3ms 3592 KiB
11 Elfogadva 3ms 3452 KiB
12 Elfogadva 3ms 3572 KiB
subtask3 0/20
13 Elfogadva 3ms 2516 KiB
14 Hibás válasz 3ms 2520 KiB
15 Futási hiba 3ms 2848 KiB
16 Hibás válasz 3ms 2788 KiB
17 Hibás válasz 3ms 2848 KiB
18 Hibás válasz 3ms 3036 KiB
19 Elfogadva 3ms 3244 KiB
20 Hibás válasz 3ms 3592 KiB
21 Elfogadva 3ms 3452 KiB
22 Elfogadva 3ms 3572 KiB
23 Futási hiba 3ms 3684 KiB
24 Futási hiba 3ms 3928 KiB
25 Hibás válasz 3ms 3940 KiB
26 Hibás válasz 3ms 4004 KiB
27 Hibás válasz 3ms 4072 KiB
28 Hibás válasz 3ms 4136 KiB
29 Elfogadva 3ms 4208 KiB
30 Hibás válasz 3ms 4212 KiB
31 Futási hiba 3ms 4168 KiB
subtask4 0/20
32 Elfogadva 3ms 2516 KiB
33 Hibás válasz 3ms 2520 KiB
34 Futási hiba 3ms 2848 KiB
35 Hibás válasz 3ms 2788 KiB
36 Hibás válasz 3ms 2848 KiB
37 Hibás válasz 3ms 3036 KiB
38 Elfogadva 3ms 3244 KiB
39 Hibás válasz 3ms 3592 KiB
40 Elfogadva 3ms 3452 KiB
41 Elfogadva 3ms 3572 KiB
42 Futási hiba 3ms 3684 KiB
43 Futási hiba 3ms 3928 KiB
44 Hibás válasz 3ms 3940 KiB
45 Hibás válasz 3ms 4004 KiB
46 Hibás válasz 3ms 4072 KiB
47 Hibás válasz 3ms 4136 KiB
48 Elfogadva 3ms 4208 KiB
49 Hibás válasz 3ms 4212 KiB
50 Futási hiba 3ms 4168 KiB
51 Futási hiba 3ms 4740 KiB
52 Futási hiba 4ms 5060 KiB
53 Futási hiba 4ms 4868 KiB
54 Futási hiba 4ms 5068 KiB
55 Futási hiba 3ms 5108 KiB
56 Hibás válasz 4ms 4892 KiB
57 Hibás válasz 3ms 4812 KiB
58 Hibás válasz 3ms 4836 KiB
59 Hibás válasz 3ms 4812 KiB
60 Hibás válasz 3ms 4816 KiB
61 Futási hiba 4ms 5416 KiB
62 Hibás válasz 3ms 5528 KiB
63 Futási hiba 3ms 5564 KiB
64 Hibás válasz 3ms 5492 KiB
65 Hibás válasz 3ms 5524 KiB
66 Futási hiba 3ms 5552 KiB
67 Hibás válasz 3ms 5376 KiB
68 Hibás válasz 3ms 5660 KiB
69 Elfogadva 3ms 5652 KiB
70 Hibás válasz 3ms 5592 KiB
subtask5 0/40
71 Elfogadva 3ms 2516 KiB
72 Hibás válasz 3ms 2520 KiB
73 Futási hiba 3ms 2848 KiB
74 Hibás válasz 3ms 2788 KiB
75 Hibás válasz 3ms 2848 KiB
76 Hibás válasz 3ms 3036 KiB
77 Elfogadva 3ms 3244 KiB
78 Hibás válasz 3ms 3592 KiB
79 Elfogadva 3ms 3452 KiB
80 Elfogadva 3ms 3572 KiB
81 Futási hiba 3ms 3684 KiB
82 Futási hiba 3ms 3928 KiB
83 Hibás válasz 3ms 3940 KiB
84 Hibás válasz 3ms 4004 KiB
85 Hibás válasz 3ms 4072 KiB
86 Hibás válasz 3ms 4136 KiB
87 Elfogadva 3ms 4208 KiB
88 Hibás válasz 3ms 4212 KiB
89 Futási hiba 3ms 4168 KiB
90 Futási hiba 3ms 4740 KiB
91 Futási hiba 4ms 5060 KiB
92 Futási hiba 4ms 4868 KiB
93 Futási hiba 4ms 5068 KiB
94 Futási hiba 3ms 5108 KiB
95 Hibás válasz 4ms 4892 KiB
96 Hibás válasz 3ms 4812 KiB
97 Hibás válasz 3ms 4836 KiB
98 Hibás válasz 3ms 4812 KiB
99 Hibás válasz 3ms 4816 KiB
100 Futási hiba 4ms 5416 KiB
101 Hibás válasz 3ms 5528 KiB
102 Futási hiba 3ms 5564 KiB
103 Hibás válasz 3ms 5492 KiB
104 Hibás válasz 3ms 5524 KiB
105 Futási hiba 3ms 5552 KiB
106 Hibás válasz 3ms 5376 KiB
107 Hibás válasz 3ms 5660 KiB
108 Elfogadva 3ms 5652 KiB
109 Hibás válasz 3ms 5592 KiB
110 Futási hiba 79ms 29828 KiB
111 Futási hiba 79ms 29920 KiB
112 Futási hiba 79ms 29776 KiB
113 Futási hiba 79ms 29780 KiB
114 Futási hiba 79ms 29704 KiB
115 Futási hiba 79ms 29808 KiB
116 Hibás válasz 82ms 29784 KiB
117 Hibás válasz 82ms 29840 KiB
118 Hibás válasz 82ms 29820 KiB
119 Hibás válasz 82ms 29688 KiB
120 Hibás válasz 82ms 29680 KiB
121 Hibás válasz 82ms 29684 KiB
122 Futási hiba 82ms 29684 KiB
123 Hibás válasz 82ms 29760 KiB
124 Futási hiba 82ms 29704 KiB
125 Hibás válasz 82ms 29812 KiB
126 Futási hiba 81ms 29684 KiB
127 Futási hiba 82ms 29688 KiB
128 Futási hiba 82ms 29680 KiB
129 Futási hiba 81ms 29772 KiB
130 Hibás válasz 81ms 29868 KiB
131 Elfogadva 101ms 29864 KiB
132 Hibás válasz 82ms 29680 KiB