109142024-04-18 20:31:22gortomiRajzcpp17Wrong answer 0/10089ms29780 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);
        return x > 0;
    }
    return xa > 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";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Wrong answer3ms2060 KiB
subtask20/20
3Wrong answer3ms2268 KiB
4Wrong answer3ms2316 KiB
5Wrong answer3ms2444 KiB
6Wrong answer3ms2676 KiB
7Wrong answer3ms2888 KiB
8Wrong answer3ms2976 KiB
9Wrong answer3ms3072 KiB
10Wrong answer3ms2980 KiB
11Accepted3ms3080 KiB
12Accepted3ms3208 KiB
subtask30/20
13Wrong answer3ms2268 KiB
14Wrong answer3ms2316 KiB
15Wrong answer3ms2444 KiB
16Wrong answer3ms2676 KiB
17Wrong answer3ms2888 KiB
18Wrong answer3ms2976 KiB
19Wrong answer3ms3072 KiB
20Wrong answer3ms2980 KiB
21Accepted3ms3080 KiB
22Accepted3ms3208 KiB
23Wrong answer3ms3180 KiB
24Wrong answer3ms3384 KiB
25Wrong answer3ms3392 KiB
26Wrong answer3ms3388 KiB
27Wrong answer3ms3384 KiB
28Wrong answer3ms3384 KiB
29Wrong answer3ms3532 KiB
30Wrong answer3ms3396 KiB
31Accepted3ms3384 KiB
subtask40/20
32Wrong answer3ms2268 KiB
33Wrong answer3ms2316 KiB
34Wrong answer3ms2444 KiB
35Wrong answer3ms2676 KiB
36Wrong answer3ms2888 KiB
37Wrong answer3ms2976 KiB
38Wrong answer3ms3072 KiB
39Wrong answer3ms2980 KiB
40Accepted3ms3080 KiB
41Accepted3ms3208 KiB
42Wrong answer3ms3180 KiB
43Wrong answer3ms3384 KiB
44Wrong answer3ms3392 KiB
45Wrong answer3ms3388 KiB
46Wrong answer3ms3384 KiB
47Wrong answer3ms3384 KiB
48Wrong answer3ms3532 KiB
49Wrong answer3ms3396 KiB
50Accepted3ms3384 KiB
51Wrong answer3ms3844 KiB
52Wrong answer3ms3848 KiB
53Wrong answer3ms3848 KiB
54Wrong answer3ms4120 KiB
55Wrong answer3ms4388 KiB
56Wrong answer3ms4272 KiB
57Wrong answer3ms4292 KiB
58Wrong answer3ms4308 KiB
59Wrong answer3ms4300 KiB
60Wrong answer3ms4304 KiB
61Wrong answer3ms4552 KiB
62Wrong answer3ms4512 KiB
63Wrong answer3ms4772 KiB
64Wrong answer3ms4772 KiB
65Wrong answer3ms4720 KiB
66Wrong answer3ms4724 KiB
67Wrong answer3ms4720 KiB
68Wrong answer3ms4716 KiB
69Wrong answer3ms4968 KiB
70Wrong answer3ms4984 KiB
subtask50/40
71Wrong answer3ms2268 KiB
72Wrong answer3ms2316 KiB
73Wrong answer3ms2444 KiB
74Wrong answer3ms2676 KiB
75Wrong answer3ms2888 KiB
76Wrong answer3ms2976 KiB
77Wrong answer3ms3072 KiB
78Wrong answer3ms2980 KiB
79Accepted3ms3080 KiB
80Accepted3ms3208 KiB
81Wrong answer3ms3180 KiB
82Wrong answer3ms3384 KiB
83Wrong answer3ms3392 KiB
84Wrong answer3ms3388 KiB
85Wrong answer3ms3384 KiB
86Wrong answer3ms3384 KiB
87Wrong answer3ms3532 KiB
88Wrong answer3ms3396 KiB
89Accepted3ms3384 KiB
90Wrong answer3ms3844 KiB
91Wrong answer3ms3848 KiB
92Wrong answer3ms3848 KiB
93Wrong answer3ms4120 KiB
94Wrong answer3ms4388 KiB
95Wrong answer3ms4272 KiB
96Wrong answer3ms4292 KiB
97Wrong answer3ms4308 KiB
98Wrong answer3ms4300 KiB
99Wrong answer3ms4304 KiB
100Wrong answer3ms4552 KiB
101Wrong answer3ms4512 KiB
102Wrong answer3ms4772 KiB
103Wrong answer3ms4772 KiB
104Wrong answer3ms4720 KiB
105Wrong answer3ms4724 KiB
106Wrong answer3ms4720 KiB
107Wrong answer3ms4716 KiB
108Wrong answer3ms4968 KiB
109Wrong answer3ms4984 KiB
110Wrong answer86ms29144 KiB
111Wrong answer86ms29152 KiB
112Wrong answer85ms29172 KiB
113Wrong answer85ms29204 KiB
114Wrong answer86ms29196 KiB
115Wrong answer85ms29200 KiB
116Wrong answer89ms29152 KiB
117Wrong answer85ms29312 KiB
118Wrong answer87ms29492 KiB
119Wrong answer89ms29496 KiB
120Wrong answer89ms29496 KiB
121Wrong answer86ms29444 KiB
122Wrong answer89ms29612 KiB
123Wrong answer87ms29576 KiB
124Wrong answer87ms29572 KiB
125Wrong answer87ms29508 KiB
126Wrong answer87ms29516 KiB
127Wrong answer87ms29512 KiB
128Wrong answer87ms29484 KiB
129Wrong answer83ms29780 KiB
130Wrong answer87ms29720 KiB
131Wrong answer68ms29652 KiB
132Wrong answer87ms29540 KiB