109082024-04-18 19:54:00gortomiRajzcpp17Wrong answer 0/10097ms29924 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 = -1;
    //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
1Wrong answer3ms1696 KiB
2Wrong answer3ms1932 KiB
subtask20/20
3Wrong answer3ms2160 KiB
4Wrong answer3ms2364 KiB
5Wrong answer3ms2584 KiB
6Wrong answer3ms2804 KiB
7Wrong answer3ms2960 KiB
8Wrong answer3ms3212 KiB
9Wrong answer3ms3276 KiB
10Wrong answer3ms3344 KiB
11Accepted3ms3448 KiB
12Accepted3ms3552 KiB
subtask30/20
13Wrong answer3ms2160 KiB
14Wrong answer3ms2364 KiB
15Wrong answer3ms2584 KiB
16Wrong answer3ms2804 KiB
17Wrong answer3ms2960 KiB
18Wrong answer3ms3212 KiB
19Wrong answer3ms3276 KiB
20Wrong answer3ms3344 KiB
21Accepted3ms3448 KiB
22Accepted3ms3552 KiB
23Wrong answer3ms3536 KiB
24Wrong answer3ms3756 KiB
25Wrong answer3ms3848 KiB
26Wrong answer3ms3840 KiB
27Wrong answer3ms3840 KiB
28Wrong answer3ms3736 KiB
29Accepted3ms3824 KiB
30Accepted3ms3820 KiB
31Wrong answer3ms3636 KiB
subtask40/20
32Wrong answer3ms2160 KiB
33Wrong answer3ms2364 KiB
34Wrong answer3ms2584 KiB
35Wrong answer3ms2804 KiB
36Wrong answer3ms2960 KiB
37Wrong answer3ms3212 KiB
38Wrong answer3ms3276 KiB
39Wrong answer3ms3344 KiB
40Accepted3ms3448 KiB
41Accepted3ms3552 KiB
42Wrong answer3ms3536 KiB
43Wrong answer3ms3756 KiB
44Wrong answer3ms3848 KiB
45Wrong answer3ms3840 KiB
46Wrong answer3ms3840 KiB
47Wrong answer3ms3736 KiB
48Accepted3ms3824 KiB
49Accepted3ms3820 KiB
50Wrong answer3ms3636 KiB
51Wrong answer4ms4096 KiB
52Wrong answer3ms4096 KiB
53Wrong answer3ms4384 KiB
54Wrong answer4ms4532 KiB
55Wrong answer3ms4408 KiB
56Wrong answer3ms4320 KiB
57Wrong answer3ms4344 KiB
58Wrong answer3ms4504 KiB
59Wrong answer4ms4552 KiB
60Wrong answer3ms4480 KiB
61Wrong answer3ms4472 KiB
62Wrong answer3ms4480 KiB
63Wrong answer3ms4732 KiB
64Wrong answer3ms4648 KiB
65Wrong answer3ms4656 KiB
66Wrong answer3ms4824 KiB
67Accepted3ms4828 KiB
68Accepted3ms4796 KiB
69Accepted3ms4756 KiB
70Accepted3ms4792 KiB
subtask50/40
71Wrong answer3ms2160 KiB
72Wrong answer3ms2364 KiB
73Wrong answer3ms2584 KiB
74Wrong answer3ms2804 KiB
75Wrong answer3ms2960 KiB
76Wrong answer3ms3212 KiB
77Wrong answer3ms3276 KiB
78Wrong answer3ms3344 KiB
79Accepted3ms3448 KiB
80Accepted3ms3552 KiB
81Wrong answer3ms3536 KiB
82Wrong answer3ms3756 KiB
83Wrong answer3ms3848 KiB
84Wrong answer3ms3840 KiB
85Wrong answer3ms3840 KiB
86Wrong answer3ms3736 KiB
87Accepted3ms3824 KiB
88Accepted3ms3820 KiB
89Wrong answer3ms3636 KiB
90Wrong answer4ms4096 KiB
91Wrong answer3ms4096 KiB
92Wrong answer3ms4384 KiB
93Wrong answer4ms4532 KiB
94Wrong answer3ms4408 KiB
95Wrong answer3ms4320 KiB
96Wrong answer3ms4344 KiB
97Wrong answer3ms4504 KiB
98Wrong answer4ms4552 KiB
99Wrong answer3ms4480 KiB
100Wrong answer3ms4472 KiB
101Wrong answer3ms4480 KiB
102Wrong answer3ms4732 KiB
103Wrong answer3ms4648 KiB
104Wrong answer3ms4656 KiB
105Wrong answer3ms4824 KiB
106Accepted3ms4828 KiB
107Accepted3ms4796 KiB
108Accepted3ms4756 KiB
109Accepted3ms4792 KiB
110Wrong answer93ms28964 KiB
111Wrong answer93ms29052 KiB
112Wrong answer92ms29056 KiB
113Wrong answer87ms29360 KiB
114Wrong answer93ms29448 KiB
115Wrong answer89ms29616 KiB
116Wrong answer96ms29792 KiB
117Wrong answer97ms29648 KiB
118Wrong answer97ms29616 KiB
119Wrong answer93ms29664 KiB
120Wrong answer96ms29588 KiB
121Wrong answer93ms29644 KiB
122Wrong answer96ms29632 KiB
123Wrong answer96ms29632 KiB
124Wrong answer96ms29628 KiB
125Wrong answer92ms29644 KiB
126Wrong answer96ms29592 KiB
127Wrong answer92ms29768 KiB
128Accepted94ms29888 KiB
129Wrong answer90ms29800 KiB
130Wrong answer94ms29924 KiB
131Accepted72ms29868 KiB
132Accepted94ms29868 KiB