109092024-04-18 20:08:04gortomiRajzcpp17Wrong answer 0/10086ms29004 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)
{
    long double b = (yb - ya) / (xb - xa);
    if(b == 0) return 0;
    long double x = xa;
    //+ (-ya / b);
    return x > 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
1Accepted3ms2104 KiB
2Wrong answer3ms2132 KiB
subtask20/20
3Accepted3ms2348 KiB
4Wrong answer3ms2480 KiB
5Runtime error3ms2796 KiB
6Wrong answer3ms2820 KiB
7Wrong answer3ms3004 KiB
8Wrong answer3ms3140 KiB
9Wrong answer3ms3220 KiB
10Accepted3ms3352 KiB
11Accepted3ms3328 KiB
12Accepted3ms3216 KiB
subtask30/20
13Accepted3ms2348 KiB
14Wrong answer3ms2480 KiB
15Runtime error3ms2796 KiB
16Wrong answer3ms2820 KiB
17Wrong answer3ms3004 KiB
18Wrong answer3ms3140 KiB
19Wrong answer3ms3220 KiB
20Accepted3ms3352 KiB
21Accepted3ms3328 KiB
22Accepted3ms3216 KiB
23Runtime error3ms3328 KiB
24Runtime error3ms3348 KiB
25Wrong answer3ms3592 KiB
26Wrong answer3ms3572 KiB
27Wrong answer3ms3784 KiB
28Wrong answer3ms3680 KiB
29Accepted3ms3676 KiB
30Wrong answer3ms3776 KiB
31Runtime error3ms4068 KiB
subtask40/20
32Accepted3ms2348 KiB
33Wrong answer3ms2480 KiB
34Runtime error3ms2796 KiB
35Wrong answer3ms2820 KiB
36Wrong answer3ms3004 KiB
37Wrong answer3ms3140 KiB
38Wrong answer3ms3220 KiB
39Accepted3ms3352 KiB
40Accepted3ms3328 KiB
41Accepted3ms3216 KiB
42Runtime error3ms3328 KiB
43Runtime error3ms3348 KiB
44Wrong answer3ms3592 KiB
45Wrong answer3ms3572 KiB
46Wrong answer3ms3784 KiB
47Wrong answer3ms3680 KiB
48Accepted3ms3676 KiB
49Wrong answer3ms3776 KiB
50Runtime error3ms4068 KiB
51Runtime error3ms4556 KiB
52Runtime error4ms4564 KiB
53Runtime error3ms4452 KiB
54Runtime error3ms4456 KiB
55Runtime error3ms4584 KiB
56Wrong answer4ms4740 KiB
57Wrong answer3ms4668 KiB
58Wrong answer3ms4588 KiB
59Wrong answer3ms4584 KiB
60Wrong answer3ms4588 KiB
61Runtime error3ms4668 KiB
62Wrong answer3ms4592 KiB
63Wrong answer3ms4592 KiB
64Wrong answer3ms4616 KiB
65Wrong answer3ms4740 KiB
66Runtime error3ms4716 KiB
67Wrong answer3ms4628 KiB
68Wrong answer3ms4664 KiB
69Accepted3ms4664 KiB
70Wrong answer3ms4660 KiB
subtask50/40
71Accepted3ms2348 KiB
72Wrong answer3ms2480 KiB
73Runtime error3ms2796 KiB
74Wrong answer3ms2820 KiB
75Wrong answer3ms3004 KiB
76Wrong answer3ms3140 KiB
77Wrong answer3ms3220 KiB
78Accepted3ms3352 KiB
79Accepted3ms3328 KiB
80Accepted3ms3216 KiB
81Runtime error3ms3328 KiB
82Runtime error3ms3348 KiB
83Wrong answer3ms3592 KiB
84Wrong answer3ms3572 KiB
85Wrong answer3ms3784 KiB
86Wrong answer3ms3680 KiB
87Accepted3ms3676 KiB
88Wrong answer3ms3776 KiB
89Runtime error3ms4068 KiB
90Runtime error3ms4556 KiB
91Runtime error4ms4564 KiB
92Runtime error3ms4452 KiB
93Runtime error3ms4456 KiB
94Runtime error3ms4584 KiB
95Wrong answer4ms4740 KiB
96Wrong answer3ms4668 KiB
97Wrong answer3ms4588 KiB
98Wrong answer3ms4584 KiB
99Wrong answer3ms4588 KiB
100Runtime error3ms4668 KiB
101Wrong answer3ms4592 KiB
102Wrong answer3ms4592 KiB
103Wrong answer3ms4616 KiB
104Wrong answer3ms4740 KiB
105Runtime error3ms4716 KiB
106Wrong answer3ms4628 KiB
107Wrong answer3ms4664 KiB
108Accepted3ms4664 KiB
109Wrong answer3ms4660 KiB
110Runtime error86ms28844 KiB
111Runtime error81ms28916 KiB
112Runtime error79ms28992 KiB
113Runtime error85ms28980 KiB
114Runtime error81ms28976 KiB
115Runtime error81ms28824 KiB
116Wrong answer82ms28900 KiB
117Wrong answer82ms28840 KiB
118Wrong answer82ms29004 KiB
119Wrong answer82ms28828 KiB
120Wrong answer82ms28868 KiB
121Wrong answer82ms28828 KiB
122Runtime error82ms28864 KiB
123Wrong answer82ms28860 KiB
124Runtime error82ms28864 KiB
125Wrong answer82ms28896 KiB
126Runtime error82ms28872 KiB
127Runtime error82ms28876 KiB
128Runtime error82ms28940 KiB
129Runtime error82ms28972 KiB
130Runtime error82ms28872 KiB
131Accepted79ms28964 KiB
132Wrong answer82ms28908 KiB