109182024-04-18 20:55:23gortomiRajzcpp17Wrong answer 0/100100ms29980 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1700 KiB
2Accepted3ms1876 KiB
subtask20/20
3Accepted3ms2084 KiB
4Wrong answer3ms2308 KiB
5Accepted2ms2380 KiB
6Accepted2ms2480 KiB
7Wrong answer3ms2504 KiB
8Accepted3ms2604 KiB
9Wrong answer3ms2732 KiB
10Wrong answer2ms2804 KiB
11Accepted2ms2796 KiB
12Accepted3ms3080 KiB
subtask30/20
13Accepted3ms2084 KiB
14Wrong answer3ms2308 KiB
15Accepted2ms2380 KiB
16Accepted2ms2480 KiB
17Wrong answer3ms2504 KiB
18Accepted3ms2604 KiB
19Wrong answer3ms2732 KiB
20Wrong answer2ms2804 KiB
21Accepted2ms2796 KiB
22Accepted3ms3080 KiB
23Accepted3ms3200 KiB
24Accepted3ms3284 KiB
25Wrong answer3ms3168 KiB
26Wrong answer3ms3512 KiB
27Accepted3ms3496 KiB
28Accepted3ms3580 KiB
29Accepted3ms3468 KiB
30Accepted3ms3600 KiB
31Accepted3ms3648 KiB
subtask40/20
32Accepted3ms2084 KiB
33Wrong answer3ms2308 KiB
34Accepted2ms2380 KiB
35Accepted2ms2480 KiB
36Wrong answer3ms2504 KiB
37Accepted3ms2604 KiB
38Wrong answer3ms2732 KiB
39Wrong answer2ms2804 KiB
40Accepted2ms2796 KiB
41Accepted3ms3080 KiB
42Accepted3ms3200 KiB
43Accepted3ms3284 KiB
44Wrong answer3ms3168 KiB
45Wrong answer3ms3512 KiB
46Accepted3ms3496 KiB
47Accepted3ms3580 KiB
48Accepted3ms3468 KiB
49Accepted3ms3600 KiB
50Accepted3ms3648 KiB
51Accepted3ms4364 KiB
52Accepted3ms4648 KiB
53Accepted3ms4532 KiB
54Accepted3ms4816 KiB
55Accepted3ms5100 KiB
56Accepted3ms5252 KiB
57Accepted3ms5096 KiB
58Accepted3ms5224 KiB
59Accepted3ms5252 KiB
60Accepted3ms5160 KiB
61Wrong answer3ms5156 KiB
62Wrong answer3ms5188 KiB
63Wrong answer3ms5196 KiB
64Wrong answer3ms5188 KiB
65Wrong answer3ms5192 KiB
66Accepted3ms5160 KiB
67Accepted4ms5188 KiB
68Accepted3ms5224 KiB
69Accepted3ms5216 KiB
70Accepted4ms5248 KiB
subtask50/40
71Accepted3ms2084 KiB
72Wrong answer3ms2308 KiB
73Accepted2ms2380 KiB
74Accepted2ms2480 KiB
75Wrong answer3ms2504 KiB
76Accepted3ms2604 KiB
77Wrong answer3ms2732 KiB
78Wrong answer2ms2804 KiB
79Accepted2ms2796 KiB
80Accepted3ms3080 KiB
81Accepted3ms3200 KiB
82Accepted3ms3284 KiB
83Wrong answer3ms3168 KiB
84Wrong answer3ms3512 KiB
85Accepted3ms3496 KiB
86Accepted3ms3580 KiB
87Accepted3ms3468 KiB
88Accepted3ms3600 KiB
89Accepted3ms3648 KiB
90Accepted3ms4364 KiB
91Accepted3ms4648 KiB
92Accepted3ms4532 KiB
93Accepted3ms4816 KiB
94Accepted3ms5100 KiB
95Accepted3ms5252 KiB
96Accepted3ms5096 KiB
97Accepted3ms5224 KiB
98Accepted3ms5252 KiB
99Accepted3ms5160 KiB
100Wrong answer3ms5156 KiB
101Wrong answer3ms5188 KiB
102Wrong answer3ms5196 KiB
103Wrong answer3ms5188 KiB
104Wrong answer3ms5192 KiB
105Accepted3ms5160 KiB
106Accepted4ms5188 KiB
107Accepted3ms5224 KiB
108Accepted3ms5216 KiB
109Accepted4ms5248 KiB
110Accepted86ms29396 KiB
111Wrong answer82ms29396 KiB
112Accepted86ms29396 KiB
113Accepted81ms29444 KiB
114Accepted86ms29444 KiB
115Wrong answer82ms29504 KiB
116Accepted89ms29448 KiB
117Accepted89ms29444 KiB
118Accepted89ms29440 KiB
119Accepted90ms29464 KiB
120Accepted89ms29612 KiB
121Accepted90ms29636 KiB
122Wrong answer85ms29816 KiB
123Wrong answer89ms29852 KiB
124Wrong answer89ms29816 KiB
125Wrong answer85ms29896 KiB
126Accepted98ms29980 KiB
127Accepted97ms29912 KiB
128Accepted100ms29916 KiB
129Accepted97ms29860 KiB
130Accepted93ms29912 KiB
131Accepted75ms29868 KiB
132Accepted98ms29868 KiB