10919 2024. 04. 18 21:54:18 gortomi Rajz cpp17 Elfogadva 100/100 98ms 30028 KiB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
int n;
int get(int v)
{
    return p[v] == 0 ? v : p[v] = get(p[v]);
}
void unio(int a, int b)
{
    a = get(a);
    b = get(b);
    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 cross(ll x1, ll y1, ll x2, ll y2)
{
    return x1 * y2 - x2 * y1 < 0;
}
bool insc(ll xa, ll xb, ll ya, ll yb)
{
    ll xd = 2e9 + 5, yd = 1, xc = 0, yc = 0;
    return (cross(xb - xa, yb - ya, xc - xa, yc - ya) != cross(xb - xa, yb - ya, xd - xa, yd - ya)) &&
        (cross(xd - xc, yd - yc, xa - xc, ya - yc) != cross(xd - xc, yd - yc, xb - xc, yb - yc));
}
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]);
        //cout << a << " " << b << " " << d << " " << g << "\n";
        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 1832 KiB
2 Elfogadva 3ms 2024 KiB
subtask2 20/20
3 Elfogadva 3ms 2240 KiB
4 Elfogadva 3ms 2464 KiB
5 Elfogadva 3ms 2556 KiB
6 Elfogadva 3ms 2776 KiB
7 Elfogadva 3ms 2984 KiB
8 Elfogadva 3ms 3108 KiB
9 Elfogadva 3ms 3336 KiB
10 Elfogadva 3ms 3532 KiB
11 Elfogadva 3ms 3616 KiB
12 Elfogadva 3ms 3768 KiB
subtask3 20/20
13 Elfogadva 3ms 2240 KiB
14 Elfogadva 3ms 2464 KiB
15 Elfogadva 3ms 2556 KiB
16 Elfogadva 3ms 2776 KiB
17 Elfogadva 3ms 2984 KiB
18 Elfogadva 3ms 3108 KiB
19 Elfogadva 3ms 3336 KiB
20 Elfogadva 3ms 3532 KiB
21 Elfogadva 3ms 3616 KiB
22 Elfogadva 3ms 3768 KiB
23 Elfogadva 3ms 4008 KiB
24 Elfogadva 3ms 4096 KiB
25 Elfogadva 3ms 4168 KiB
26 Elfogadva 3ms 4292 KiB
27 Elfogadva 3ms 4376 KiB
28 Elfogadva 3ms 4376 KiB
29 Elfogadva 3ms 4356 KiB
30 Elfogadva 3ms 4444 KiB
31 Elfogadva 3ms 4412 KiB
subtask4 20/20
32 Elfogadva 3ms 2240 KiB
33 Elfogadva 3ms 2464 KiB
34 Elfogadva 3ms 2556 KiB
35 Elfogadva 3ms 2776 KiB
36 Elfogadva 3ms 2984 KiB
37 Elfogadva 3ms 3108 KiB
38 Elfogadva 3ms 3336 KiB
39 Elfogadva 3ms 3532 KiB
40 Elfogadva 3ms 3616 KiB
41 Elfogadva 3ms 3768 KiB
42 Elfogadva 3ms 4008 KiB
43 Elfogadva 3ms 4096 KiB
44 Elfogadva 3ms 4168 KiB
45 Elfogadva 3ms 4292 KiB
46 Elfogadva 3ms 4376 KiB
47 Elfogadva 3ms 4376 KiB
48 Elfogadva 3ms 4356 KiB
49 Elfogadva 3ms 4444 KiB
50 Elfogadva 3ms 4412 KiB
51 Elfogadva 4ms 5040 KiB
52 Elfogadva 3ms 5324 KiB
53 Elfogadva 3ms 5280 KiB
54 Elfogadva 3ms 5236 KiB
55 Elfogadva 3ms 5228 KiB
56 Elfogadva 3ms 5520 KiB
57 Elfogadva 3ms 5488 KiB
58 Elfogadva 3ms 5492 KiB
59 Elfogadva 3ms 5512 KiB
60 Elfogadva 3ms 5548 KiB
61 Elfogadva 3ms 5500 KiB
62 Elfogadva 3ms 5472 KiB
63 Elfogadva 3ms 5472 KiB
64 Elfogadva 3ms 5508 KiB
65 Elfogadva 3ms 5416 KiB
66 Elfogadva 3ms 5420 KiB
67 Elfogadva 3ms 5672 KiB
68 Elfogadva 3ms 5628 KiB
69 Elfogadva 3ms 5656 KiB
70 Elfogadva 3ms 5660 KiB
subtask5 40/40
71 Elfogadva 3ms 2240 KiB
72 Elfogadva 3ms 2464 KiB
73 Elfogadva 3ms 2556 KiB
74 Elfogadva 3ms 2776 KiB
75 Elfogadva 3ms 2984 KiB
76 Elfogadva 3ms 3108 KiB
77 Elfogadva 3ms 3336 KiB
78 Elfogadva 3ms 3532 KiB
79 Elfogadva 3ms 3616 KiB
80 Elfogadva 3ms 3768 KiB
81 Elfogadva 3ms 4008 KiB
82 Elfogadva 3ms 4096 KiB
83 Elfogadva 3ms 4168 KiB
84 Elfogadva 3ms 4292 KiB
85 Elfogadva 3ms 4376 KiB
86 Elfogadva 3ms 4376 KiB
87 Elfogadva 3ms 4356 KiB
88 Elfogadva 3ms 4444 KiB
89 Elfogadva 3ms 4412 KiB
90 Elfogadva 4ms 5040 KiB
91 Elfogadva 3ms 5324 KiB
92 Elfogadva 3ms 5280 KiB
93 Elfogadva 3ms 5236 KiB
94 Elfogadva 3ms 5228 KiB
95 Elfogadva 3ms 5520 KiB
96 Elfogadva 3ms 5488 KiB
97 Elfogadva 3ms 5492 KiB
98 Elfogadva 3ms 5512 KiB
99 Elfogadva 3ms 5548 KiB
100 Elfogadva 3ms 5500 KiB
101 Elfogadva 3ms 5472 KiB
102 Elfogadva 3ms 5472 KiB
103 Elfogadva 3ms 5508 KiB
104 Elfogadva 3ms 5416 KiB
105 Elfogadva 3ms 5420 KiB
106 Elfogadva 3ms 5672 KiB
107 Elfogadva 3ms 5628 KiB
108 Elfogadva 3ms 5656 KiB
109 Elfogadva 3ms 5660 KiB
110 Elfogadva 81ms 29864 KiB
111 Elfogadva 85ms 29864 KiB
112 Elfogadva 86ms 29872 KiB
113 Elfogadva 86ms 29864 KiB
114 Elfogadva 86ms 29868 KiB
115 Elfogadva 81ms 29864 KiB
116 Elfogadva 83ms 29936 KiB
117 Elfogadva 83ms 30028 KiB
118 Elfogadva 83ms 29936 KiB
119 Elfogadva 86ms 29868 KiB
120 Elfogadva 85ms 29868 KiB
121 Elfogadva 85ms 29868 KiB
122 Elfogadva 83ms 29868 KiB
123 Elfogadva 85ms 29756 KiB
124 Elfogadva 89ms 29940 KiB
125 Elfogadva 85ms 29864 KiB
126 Elfogadva 97ms 29868 KiB
127 Elfogadva 92ms 29916 KiB
128 Elfogadva 98ms 29868 KiB
129 Elfogadva 90ms 29916 KiB
130 Elfogadva 96ms 29964 KiB
131 Elfogadva 75ms 29976 KiB
132 Elfogadva 98ms 29944 KiB