109122024-04-18 20:21:22gortomiRajzcpp17Wrong answer 0/10090ms29824 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(xb != xa)
    {
        long double b = (yb - ya) / (xb - xa);
        if(b == 0) return 0;
        long double x = xa + (-ya / b);
        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
1Accepted3ms1832 KiB
2Wrong answer3ms2024 KiB
subtask20/20
3Accepted3ms2236 KiB
4Wrong answer3ms2456 KiB
5Wrong answer3ms2664 KiB
6Wrong answer3ms2752 KiB
7Wrong answer3ms2964 KiB
8Wrong answer3ms2956 KiB
9Accepted3ms3052 KiB
10Wrong answer3ms2952 KiB
11Accepted3ms3212 KiB
12Accepted3ms3300 KiB
subtask30/20
13Accepted3ms2236 KiB
14Wrong answer3ms2456 KiB
15Wrong answer3ms2664 KiB
16Wrong answer3ms2752 KiB
17Wrong answer3ms2964 KiB
18Wrong answer3ms2956 KiB
19Accepted3ms3052 KiB
20Wrong answer3ms2952 KiB
21Accepted3ms3212 KiB
22Accepted3ms3300 KiB
23Wrong answer3ms3228 KiB
24Wrong answer3ms3264 KiB
25Wrong answer3ms3392 KiB
26Wrong answer3ms3364 KiB
27Wrong answer3ms3496 KiB
28Wrong answer3ms3420 KiB
29Accepted3ms3512 KiB
30Wrong answer3ms3604 KiB
31Accepted3ms3596 KiB
subtask40/20
32Accepted3ms2236 KiB
33Wrong answer3ms2456 KiB
34Wrong answer3ms2664 KiB
35Wrong answer3ms2752 KiB
36Wrong answer3ms2964 KiB
37Wrong answer3ms2956 KiB
38Accepted3ms3052 KiB
39Wrong answer3ms2952 KiB
40Accepted3ms3212 KiB
41Accepted3ms3300 KiB
42Wrong answer3ms3228 KiB
43Wrong answer3ms3264 KiB
44Wrong answer3ms3392 KiB
45Wrong answer3ms3364 KiB
46Wrong answer3ms3496 KiB
47Wrong answer3ms3420 KiB
48Accepted3ms3512 KiB
49Wrong answer3ms3604 KiB
50Accepted3ms3596 KiB
51Wrong answer3ms4204 KiB
52Wrong answer3ms4232 KiB
53Wrong answer3ms4232 KiB
54Wrong answer3ms4520 KiB
55Wrong answer3ms4768 KiB
56Wrong answer3ms4640 KiB
57Wrong answer3ms4596 KiB
58Wrong answer3ms4576 KiB
59Wrong answer4ms4824 KiB
60Wrong answer3ms5012 KiB
61Wrong answer3ms4864 KiB
62Wrong answer3ms4880 KiB
63Wrong answer3ms4904 KiB
64Wrong answer3ms5176 KiB
65Wrong answer3ms5128 KiB
66Wrong answer3ms5132 KiB
67Wrong answer3ms5032 KiB
68Wrong answer3ms5048 KiB
69Accepted3ms5004 KiB
70Wrong answer3ms5032 KiB
subtask50/40
71Accepted3ms2236 KiB
72Wrong answer3ms2456 KiB
73Wrong answer3ms2664 KiB
74Wrong answer3ms2752 KiB
75Wrong answer3ms2964 KiB
76Wrong answer3ms2956 KiB
77Accepted3ms3052 KiB
78Wrong answer3ms2952 KiB
79Accepted3ms3212 KiB
80Accepted3ms3300 KiB
81Wrong answer3ms3228 KiB
82Wrong answer3ms3264 KiB
83Wrong answer3ms3392 KiB
84Wrong answer3ms3364 KiB
85Wrong answer3ms3496 KiB
86Wrong answer3ms3420 KiB
87Accepted3ms3512 KiB
88Wrong answer3ms3604 KiB
89Accepted3ms3596 KiB
90Wrong answer3ms4204 KiB
91Wrong answer3ms4232 KiB
92Wrong answer3ms4232 KiB
93Wrong answer3ms4520 KiB
94Wrong answer3ms4768 KiB
95Wrong answer3ms4640 KiB
96Wrong answer3ms4596 KiB
97Wrong answer3ms4576 KiB
98Wrong answer4ms4824 KiB
99Wrong answer3ms5012 KiB
100Wrong answer3ms4864 KiB
101Wrong answer3ms4880 KiB
102Wrong answer3ms4904 KiB
103Wrong answer3ms5176 KiB
104Wrong answer3ms5128 KiB
105Wrong answer3ms5132 KiB
106Wrong answer3ms5032 KiB
107Wrong answer3ms5048 KiB
108Accepted3ms5004 KiB
109Wrong answer3ms5032 KiB
110Wrong answer81ms29244 KiB
111Wrong answer85ms29436 KiB
112Wrong answer82ms29544 KiB
113Wrong answer85ms29596 KiB
114Wrong answer82ms29596 KiB
115Wrong answer81ms29504 KiB
116Wrong answer89ms29500 KiB
117Wrong answer85ms29552 KiB
118Wrong answer83ms29552 KiB
119Wrong answer90ms29736 KiB
120Wrong answer86ms29768 KiB
121Wrong answer85ms29764 KiB
122Wrong answer83ms29740 KiB
123Wrong answer83ms29824 KiB
124Wrong answer83ms29816 KiB
125Wrong answer83ms29772 KiB
126Wrong answer83ms29712 KiB
127Wrong answer83ms29716 KiB
128Wrong answer83ms29704 KiB
129Wrong answer82ms29720 KiB
130Wrong answer82ms29676 KiB
131Accepted79ms29732 KiB
132Wrong answer83ms29680 KiB