109042024-04-18 19:48:56gortomiRajzcpp17Wrong answer 0/100101ms29920 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
int n;
int get(int v)
{
    if(v > 2 * n || v <= 0) cout << "-1" << endl;
    return p[v] == 0 ? v : p[v] = get(p[v]);
}
void unio(int a, int b)
{
    a = get(a);
    b = get(b);
    if(a > 2 * n || b > 2 * n || a == 0 || b == 0) cout << "-1" << endl;
    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
1Accepted3ms1828 KiB
2Wrong answer3ms2064 KiB
subtask20/20
3Accepted3ms2516 KiB
4Wrong answer3ms2520 KiB
5Runtime error3ms2848 KiB
6Wrong answer3ms2788 KiB
7Wrong answer3ms2848 KiB
8Wrong answer3ms3036 KiB
9Accepted3ms3244 KiB
10Wrong answer3ms3592 KiB
11Accepted3ms3452 KiB
12Accepted3ms3572 KiB
subtask30/20
13Accepted3ms2516 KiB
14Wrong answer3ms2520 KiB
15Runtime error3ms2848 KiB
16Wrong answer3ms2788 KiB
17Wrong answer3ms2848 KiB
18Wrong answer3ms3036 KiB
19Accepted3ms3244 KiB
20Wrong answer3ms3592 KiB
21Accepted3ms3452 KiB
22Accepted3ms3572 KiB
23Runtime error3ms3684 KiB
24Runtime error3ms3928 KiB
25Wrong answer3ms3940 KiB
26Wrong answer3ms4004 KiB
27Wrong answer3ms4072 KiB
28Wrong answer3ms4136 KiB
29Accepted3ms4208 KiB
30Wrong answer3ms4212 KiB
31Runtime error3ms4168 KiB
subtask40/20
32Accepted3ms2516 KiB
33Wrong answer3ms2520 KiB
34Runtime error3ms2848 KiB
35Wrong answer3ms2788 KiB
36Wrong answer3ms2848 KiB
37Wrong answer3ms3036 KiB
38Accepted3ms3244 KiB
39Wrong answer3ms3592 KiB
40Accepted3ms3452 KiB
41Accepted3ms3572 KiB
42Runtime error3ms3684 KiB
43Runtime error3ms3928 KiB
44Wrong answer3ms3940 KiB
45Wrong answer3ms4004 KiB
46Wrong answer3ms4072 KiB
47Wrong answer3ms4136 KiB
48Accepted3ms4208 KiB
49Wrong answer3ms4212 KiB
50Runtime error3ms4168 KiB
51Runtime error3ms4740 KiB
52Runtime error4ms5060 KiB
53Runtime error4ms4868 KiB
54Runtime error4ms5068 KiB
55Runtime error3ms5108 KiB
56Wrong answer4ms4892 KiB
57Wrong answer3ms4812 KiB
58Wrong answer3ms4836 KiB
59Wrong answer3ms4812 KiB
60Wrong answer3ms4816 KiB
61Runtime error4ms5416 KiB
62Wrong answer3ms5528 KiB
63Runtime error3ms5564 KiB
64Wrong answer3ms5492 KiB
65Wrong answer3ms5524 KiB
66Runtime error3ms5552 KiB
67Wrong answer3ms5376 KiB
68Wrong answer3ms5660 KiB
69Accepted3ms5652 KiB
70Wrong answer3ms5592 KiB
subtask50/40
71Accepted3ms2516 KiB
72Wrong answer3ms2520 KiB
73Runtime error3ms2848 KiB
74Wrong answer3ms2788 KiB
75Wrong answer3ms2848 KiB
76Wrong answer3ms3036 KiB
77Accepted3ms3244 KiB
78Wrong answer3ms3592 KiB
79Accepted3ms3452 KiB
80Accepted3ms3572 KiB
81Runtime error3ms3684 KiB
82Runtime error3ms3928 KiB
83Wrong answer3ms3940 KiB
84Wrong answer3ms4004 KiB
85Wrong answer3ms4072 KiB
86Wrong answer3ms4136 KiB
87Accepted3ms4208 KiB
88Wrong answer3ms4212 KiB
89Runtime error3ms4168 KiB
90Runtime error3ms4740 KiB
91Runtime error4ms5060 KiB
92Runtime error4ms4868 KiB
93Runtime error4ms5068 KiB
94Runtime error3ms5108 KiB
95Wrong answer4ms4892 KiB
96Wrong answer3ms4812 KiB
97Wrong answer3ms4836 KiB
98Wrong answer3ms4812 KiB
99Wrong answer3ms4816 KiB
100Runtime error4ms5416 KiB
101Wrong answer3ms5528 KiB
102Runtime error3ms5564 KiB
103Wrong answer3ms5492 KiB
104Wrong answer3ms5524 KiB
105Runtime error3ms5552 KiB
106Wrong answer3ms5376 KiB
107Wrong answer3ms5660 KiB
108Accepted3ms5652 KiB
109Wrong answer3ms5592 KiB
110Runtime error79ms29828 KiB
111Runtime error79ms29920 KiB
112Runtime error79ms29776 KiB
113Runtime error79ms29780 KiB
114Runtime error79ms29704 KiB
115Runtime error79ms29808 KiB
116Wrong answer82ms29784 KiB
117Wrong answer82ms29840 KiB
118Wrong answer82ms29820 KiB
119Wrong answer82ms29688 KiB
120Wrong answer82ms29680 KiB
121Wrong answer82ms29684 KiB
122Runtime error82ms29684 KiB
123Wrong answer82ms29760 KiB
124Runtime error82ms29704 KiB
125Wrong answer82ms29812 KiB
126Runtime error81ms29684 KiB
127Runtime error82ms29688 KiB
128Runtime error82ms29680 KiB
129Runtime error81ms29772 KiB
130Wrong answer81ms29868 KiB
131Accepted101ms29864 KiB
132Wrong answer82ms29680 KiB