10918 2024. 04. 18 20:55:23 gortomi Rajz cpp17 Hibás válasz 0/100 100ms 29980 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 insc(ll xa, ll xb, ll ya, ll yb)
{
    if(ya == yb) return 0;
    if(xb != xa)
    {
        ll x = xa * (yb - ya) + -ya * (xb - xa);
        ll l = xa * (yb - ya), r = xb * (yb - ya);
        if(l > r) swap(l, r);
        return ((x > 0) ^ (ya > yb)) && x >= l && x <= r;
    }
    if(ya > yb) swap(ya, yb);
    return xa > 0 && ya <= 0 && yb >= 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]);
        //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 1700 KiB
2 Elfogadva 3ms 1876 KiB
subtask2 0/20
3 Elfogadva 3ms 2084 KiB
4 Hibás válasz 3ms 2308 KiB
5 Elfogadva 2ms 2380 KiB
6 Elfogadva 2ms 2480 KiB
7 Hibás válasz 3ms 2504 KiB
8 Elfogadva 3ms 2604 KiB
9 Hibás válasz 3ms 2732 KiB
10 Hibás válasz 2ms 2804 KiB
11 Elfogadva 2ms 2796 KiB
12 Elfogadva 3ms 3080 KiB
subtask3 0/20
13 Elfogadva 3ms 2084 KiB
14 Hibás válasz 3ms 2308 KiB
15 Elfogadva 2ms 2380 KiB
16 Elfogadva 2ms 2480 KiB
17 Hibás válasz 3ms 2504 KiB
18 Elfogadva 3ms 2604 KiB
19 Hibás válasz 3ms 2732 KiB
20 Hibás válasz 2ms 2804 KiB
21 Elfogadva 2ms 2796 KiB
22 Elfogadva 3ms 3080 KiB
23 Elfogadva 3ms 3200 KiB
24 Elfogadva 3ms 3284 KiB
25 Hibás válasz 3ms 3168 KiB
26 Hibás válasz 3ms 3512 KiB
27 Elfogadva 3ms 3496 KiB
28 Elfogadva 3ms 3580 KiB
29 Elfogadva 3ms 3468 KiB
30 Elfogadva 3ms 3600 KiB
31 Elfogadva 3ms 3648 KiB
subtask4 0/20
32 Elfogadva 3ms 2084 KiB
33 Hibás válasz 3ms 2308 KiB
34 Elfogadva 2ms 2380 KiB
35 Elfogadva 2ms 2480 KiB
36 Hibás válasz 3ms 2504 KiB
37 Elfogadva 3ms 2604 KiB
38 Hibás válasz 3ms 2732 KiB
39 Hibás válasz 2ms 2804 KiB
40 Elfogadva 2ms 2796 KiB
41 Elfogadva 3ms 3080 KiB
42 Elfogadva 3ms 3200 KiB
43 Elfogadva 3ms 3284 KiB
44 Hibás válasz 3ms 3168 KiB
45 Hibás válasz 3ms 3512 KiB
46 Elfogadva 3ms 3496 KiB
47 Elfogadva 3ms 3580 KiB
48 Elfogadva 3ms 3468 KiB
49 Elfogadva 3ms 3600 KiB
50 Elfogadva 3ms 3648 KiB
51 Elfogadva 3ms 4364 KiB
52 Elfogadva 3ms 4648 KiB
53 Elfogadva 3ms 4532 KiB
54 Elfogadva 3ms 4816 KiB
55 Elfogadva 3ms 5100 KiB
56 Elfogadva 3ms 5252 KiB
57 Elfogadva 3ms 5096 KiB
58 Elfogadva 3ms 5224 KiB
59 Elfogadva 3ms 5252 KiB
60 Elfogadva 3ms 5160 KiB
61 Hibás válasz 3ms 5156 KiB
62 Hibás válasz 3ms 5188 KiB
63 Hibás válasz 3ms 5196 KiB
64 Hibás válasz 3ms 5188 KiB
65 Hibás válasz 3ms 5192 KiB
66 Elfogadva 3ms 5160 KiB
67 Elfogadva 4ms 5188 KiB
68 Elfogadva 3ms 5224 KiB
69 Elfogadva 3ms 5216 KiB
70 Elfogadva 4ms 5248 KiB
subtask5 0/40
71 Elfogadva 3ms 2084 KiB
72 Hibás válasz 3ms 2308 KiB
73 Elfogadva 2ms 2380 KiB
74 Elfogadva 2ms 2480 KiB
75 Hibás válasz 3ms 2504 KiB
76 Elfogadva 3ms 2604 KiB
77 Hibás válasz 3ms 2732 KiB
78 Hibás válasz 2ms 2804 KiB
79 Elfogadva 2ms 2796 KiB
80 Elfogadva 3ms 3080 KiB
81 Elfogadva 3ms 3200 KiB
82 Elfogadva 3ms 3284 KiB
83 Hibás válasz 3ms 3168 KiB
84 Hibás válasz 3ms 3512 KiB
85 Elfogadva 3ms 3496 KiB
86 Elfogadva 3ms 3580 KiB
87 Elfogadva 3ms 3468 KiB
88 Elfogadva 3ms 3600 KiB
89 Elfogadva 3ms 3648 KiB
90 Elfogadva 3ms 4364 KiB
91 Elfogadva 3ms 4648 KiB
92 Elfogadva 3ms 4532 KiB
93 Elfogadva 3ms 4816 KiB
94 Elfogadva 3ms 5100 KiB
95 Elfogadva 3ms 5252 KiB
96 Elfogadva 3ms 5096 KiB
97 Elfogadva 3ms 5224 KiB
98 Elfogadva 3ms 5252 KiB
99 Elfogadva 3ms 5160 KiB
100 Hibás válasz 3ms 5156 KiB
101 Hibás válasz 3ms 5188 KiB
102 Hibás válasz 3ms 5196 KiB
103 Hibás válasz 3ms 5188 KiB
104 Hibás válasz 3ms 5192 KiB
105 Elfogadva 3ms 5160 KiB
106 Elfogadva 4ms 5188 KiB
107 Elfogadva 3ms 5224 KiB
108 Elfogadva 3ms 5216 KiB
109 Elfogadva 4ms 5248 KiB
110 Elfogadva 86ms 29396 KiB
111 Hibás válasz 82ms 29396 KiB
112 Elfogadva 86ms 29396 KiB
113 Elfogadva 81ms 29444 KiB
114 Elfogadva 86ms 29444 KiB
115 Hibás válasz 82ms 29504 KiB
116 Elfogadva 89ms 29448 KiB
117 Elfogadva 89ms 29444 KiB
118 Elfogadva 89ms 29440 KiB
119 Elfogadva 90ms 29464 KiB
120 Elfogadva 89ms 29612 KiB
121 Elfogadva 90ms 29636 KiB
122 Hibás válasz 85ms 29816 KiB
123 Hibás válasz 89ms 29852 KiB
124 Hibás válasz 89ms 29816 KiB
125 Hibás válasz 85ms 29896 KiB
126 Elfogadva 98ms 29980 KiB
127 Elfogadva 97ms 29912 KiB
128 Elfogadva 100ms 29916 KiB
129 Elfogadva 97ms 29860 KiB
130 Elfogadva 93ms 29912 KiB
131 Elfogadva 75ms 29868 KiB
132 Elfogadva 98ms 29868 KiB