109172024-04-18 20:52:47gortomiRajzcpp17Wrong answer 0/100103ms30080 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);
        ll l = xa * (yb - ya), r = xb * (yb - ya);
        if(l > r) swap(l, r);
        return ((x > 0) ^ (ya > yb)) && x >= l && x <= r;
    }
    return xa > 0 && max(ya, yb) >= 0 && min(ya, yb) <= 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]);
        //cout << a << " " << b << " " << d << " " << g << "\n";
        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
2Accepted3ms2072 KiB
subtask20/20
3Accepted3ms2284 KiB
4Wrong answer3ms2492 KiB
5Accepted3ms2676 KiB
6Accepted2ms2756 KiB
7Wrong answer3ms2872 KiB
8Accepted3ms2956 KiB
9Wrong answer3ms3084 KiB
10Wrong answer3ms3184 KiB
11Accepted3ms3508 KiB
12Accepted3ms3416 KiB
subtask30/20
13Accepted3ms2284 KiB
14Wrong answer3ms2492 KiB
15Accepted3ms2676 KiB
16Accepted2ms2756 KiB
17Wrong answer3ms2872 KiB
18Accepted3ms2956 KiB
19Wrong answer3ms3084 KiB
20Wrong answer3ms3184 KiB
21Accepted3ms3508 KiB
22Accepted3ms3416 KiB
23Accepted3ms3332 KiB
24Accepted3ms3408 KiB
25Wrong answer3ms3620 KiB
26Wrong answer3ms3616 KiB
27Accepted3ms4112 KiB
28Accepted3ms3888 KiB
29Accepted3ms3908 KiB
30Accepted3ms3988 KiB
31Accepted3ms3976 KiB
subtask40/20
32Accepted3ms2284 KiB
33Wrong answer3ms2492 KiB
34Accepted3ms2676 KiB
35Accepted2ms2756 KiB
36Wrong answer3ms2872 KiB
37Accepted3ms2956 KiB
38Wrong answer3ms3084 KiB
39Wrong answer3ms3184 KiB
40Accepted3ms3508 KiB
41Accepted3ms3416 KiB
42Accepted3ms3332 KiB
43Accepted3ms3408 KiB
44Wrong answer3ms3620 KiB
45Wrong answer3ms3616 KiB
46Accepted3ms4112 KiB
47Accepted3ms3888 KiB
48Accepted3ms3908 KiB
49Accepted3ms3988 KiB
50Accepted3ms3976 KiB
51Accepted3ms4308 KiB
52Accepted3ms4312 KiB
53Accepted4ms4564 KiB
54Accepted3ms4592 KiB
55Accepted3ms4588 KiB
56Accepted3ms4520 KiB
57Accepted3ms4528 KiB
58Accepted4ms4816 KiB
59Accepted3ms5044 KiB
60Accepted3ms4780 KiB
61Wrong answer3ms4792 KiB
62Wrong answer3ms4940 KiB
63Wrong answer3ms4908 KiB
64Wrong answer3ms5188 KiB
65Wrong answer3ms5444 KiB
66Accepted3ms5340 KiB
67Accepted3ms5344 KiB
68Accepted4ms5392 KiB
69Accepted3ms5248 KiB
70Accepted4ms5172 KiB
subtask50/40
71Accepted3ms2284 KiB
72Wrong answer3ms2492 KiB
73Accepted3ms2676 KiB
74Accepted2ms2756 KiB
75Wrong answer3ms2872 KiB
76Accepted3ms2956 KiB
77Wrong answer3ms3084 KiB
78Wrong answer3ms3184 KiB
79Accepted3ms3508 KiB
80Accepted3ms3416 KiB
81Accepted3ms3332 KiB
82Accepted3ms3408 KiB
83Wrong answer3ms3620 KiB
84Wrong answer3ms3616 KiB
85Accepted3ms4112 KiB
86Accepted3ms3888 KiB
87Accepted3ms3908 KiB
88Accepted3ms3988 KiB
89Accepted3ms3976 KiB
90Accepted3ms4308 KiB
91Accepted3ms4312 KiB
92Accepted4ms4564 KiB
93Accepted3ms4592 KiB
94Accepted3ms4588 KiB
95Accepted3ms4520 KiB
96Accepted3ms4528 KiB
97Accepted4ms4816 KiB
98Accepted3ms5044 KiB
99Accepted3ms4780 KiB
100Wrong answer3ms4792 KiB
101Wrong answer3ms4940 KiB
102Wrong answer3ms4908 KiB
103Wrong answer3ms5188 KiB
104Wrong answer3ms5444 KiB
105Accepted3ms5340 KiB
106Accepted3ms5344 KiB
107Accepted4ms5392 KiB
108Accepted3ms5248 KiB
109Accepted4ms5172 KiB
110Accepted89ms29408 KiB
111Wrong answer81ms29448 KiB
112Accepted86ms29584 KiB
113Accepted86ms29620 KiB
114Accepted86ms29584 KiB
115Wrong answer82ms29516 KiB
116Accepted90ms29600 KiB
117Accepted85ms29776 KiB
118Accepted83ms29780 KiB
119Accepted90ms29712 KiB
120Accepted90ms29708 KiB
121Accepted90ms29764 KiB
122Wrong answer90ms29712 KiB
123Wrong answer85ms29856 KiB
124Wrong answer83ms30028 KiB
125Wrong answer83ms30024 KiB
126Accepted93ms30024 KiB
127Accepted93ms30020 KiB
128Accepted100ms30024 KiB
129Accepted93ms30020 KiB
130Accepted97ms30024 KiB
131Accepted75ms30080 KiB
132Accepted103ms30080 KiB