109132024-04-18 20:27:00gortomiRajzcpp17Wrong answer 0/10087ms29924 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)
    {
        double b = (yb - ya) / double(xb - xa);
        if(b == 0) return 0;
        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
1Accepted3ms1696 KiB
2Wrong answer3ms1864 KiB
subtask20/20
3Wrong answer3ms2080 KiB
4Wrong answer3ms2300 KiB
5Wrong answer3ms2516 KiB
6Wrong answer3ms2720 KiB
7Wrong answer3ms2932 KiB
8Wrong answer3ms2992 KiB
9Accepted3ms3216 KiB
10Wrong answer3ms3220 KiB
11Accepted3ms3300 KiB
12Accepted3ms3328 KiB
subtask30/20
13Wrong answer3ms2080 KiB
14Wrong answer3ms2300 KiB
15Wrong answer3ms2516 KiB
16Wrong answer3ms2720 KiB
17Wrong answer3ms2932 KiB
18Wrong answer3ms2992 KiB
19Accepted3ms3216 KiB
20Wrong answer3ms3220 KiB
21Accepted3ms3300 KiB
22Accepted3ms3328 KiB
23Wrong answer3ms3552 KiB
24Wrong answer3ms3636 KiB
25Wrong answer3ms3636 KiB
26Wrong answer3ms3640 KiB
27Wrong answer3ms3632 KiB
28Wrong answer3ms3724 KiB
29Wrong answer3ms3768 KiB
30Wrong answer3ms3996 KiB
31Accepted2ms3948 KiB
subtask40/20
32Wrong answer3ms2080 KiB
33Wrong answer3ms2300 KiB
34Wrong answer3ms2516 KiB
35Wrong answer3ms2720 KiB
36Wrong answer3ms2932 KiB
37Wrong answer3ms2992 KiB
38Accepted3ms3216 KiB
39Wrong answer3ms3220 KiB
40Accepted3ms3300 KiB
41Accepted3ms3328 KiB
42Wrong answer3ms3552 KiB
43Wrong answer3ms3636 KiB
44Wrong answer3ms3636 KiB
45Wrong answer3ms3640 KiB
46Wrong answer3ms3632 KiB
47Wrong answer3ms3724 KiB
48Wrong answer3ms3768 KiB
49Wrong answer3ms3996 KiB
50Accepted2ms3948 KiB
51Wrong answer3ms4292 KiB
52Wrong answer4ms4644 KiB
53Wrong answer3ms4512 KiB
54Wrong answer3ms4664 KiB
55Wrong answer3ms4620 KiB
56Wrong answer3ms4624 KiB
57Wrong answer3ms4620 KiB
58Wrong answer3ms4664 KiB
59Wrong answer3ms4648 KiB
60Wrong answer3ms4540 KiB
61Wrong answer3ms4564 KiB
62Wrong answer3ms4600 KiB
63Wrong answer3ms4536 KiB
64Wrong answer3ms4836 KiB
65Wrong answer3ms5008 KiB
66Wrong answer3ms5092 KiB
67Wrong answer3ms5280 KiB
68Wrong answer3ms5240 KiB
69Accepted3ms5240 KiB
70Wrong answer3ms5240 KiB
subtask50/40
71Wrong answer3ms2080 KiB
72Wrong answer3ms2300 KiB
73Wrong answer3ms2516 KiB
74Wrong answer3ms2720 KiB
75Wrong answer3ms2932 KiB
76Wrong answer3ms2992 KiB
77Accepted3ms3216 KiB
78Wrong answer3ms3220 KiB
79Accepted3ms3300 KiB
80Accepted3ms3328 KiB
81Wrong answer3ms3552 KiB
82Wrong answer3ms3636 KiB
83Wrong answer3ms3636 KiB
84Wrong answer3ms3640 KiB
85Wrong answer3ms3632 KiB
86Wrong answer3ms3724 KiB
87Wrong answer3ms3768 KiB
88Wrong answer3ms3996 KiB
89Accepted2ms3948 KiB
90Wrong answer3ms4292 KiB
91Wrong answer4ms4644 KiB
92Wrong answer3ms4512 KiB
93Wrong answer3ms4664 KiB
94Wrong answer3ms4620 KiB
95Wrong answer3ms4624 KiB
96Wrong answer3ms4620 KiB
97Wrong answer3ms4664 KiB
98Wrong answer3ms4648 KiB
99Wrong answer3ms4540 KiB
100Wrong answer3ms4564 KiB
101Wrong answer3ms4600 KiB
102Wrong answer3ms4536 KiB
103Wrong answer3ms4836 KiB
104Wrong answer3ms5008 KiB
105Wrong answer3ms5092 KiB
106Wrong answer3ms5280 KiB
107Wrong answer3ms5240 KiB
108Accepted3ms5240 KiB
109Wrong answer3ms5240 KiB
110Wrong answer86ms29476 KiB
111Wrong answer81ms29452 KiB
112Wrong answer85ms29504 KiB
113Wrong answer85ms29548 KiB
114Wrong answer86ms29580 KiB
115Wrong answer85ms29636 KiB
116Wrong answer83ms29684 KiB
117Wrong answer83ms29704 KiB
118Wrong answer82ms29712 KiB
119Wrong answer87ms29644 KiB
120Wrong answer83ms29644 KiB
121Wrong answer83ms29644 KiB
122Wrong answer87ms29692 KiB
123Wrong answer83ms29692 KiB
124Wrong answer82ms29640 KiB
125Wrong answer87ms29704 KiB
126Wrong answer86ms29652 KiB
127Wrong answer82ms29708 KiB
128Wrong answer86ms29660 KiB
129Wrong answer82ms29704 KiB
130Wrong answer86ms29884 KiB
131Accepted78ms29924 KiB
132Wrong answer82ms29864 KiB