109052024-04-18 19:51:26gortomiRajzcpp17Wrong answer 0/100101ms30028 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
int n;
int get(int v)
{
    if(p[v] == v) 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 != 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
3Accepted3ms2244 KiB
4Wrong answer3ms2444 KiB
5Runtime error3ms2760 KiB
6Wrong answer3ms2916 KiB
7Wrong answer3ms3088 KiB
8Wrong answer3ms3316 KiB
9Accepted2ms3196 KiB
10Wrong answer3ms3324 KiB
11Accepted2ms3420 KiB
12Accepted3ms3552 KiB
subtask30/20
13Accepted3ms2244 KiB
14Wrong answer3ms2444 KiB
15Runtime error3ms2760 KiB
16Wrong answer3ms2916 KiB
17Wrong answer3ms3088 KiB
18Wrong answer3ms3316 KiB
19Accepted2ms3196 KiB
20Wrong answer3ms3324 KiB
21Accepted2ms3420 KiB
22Accepted3ms3552 KiB
23Runtime error3ms3860 KiB
24Runtime error3ms3972 KiB
25Wrong answer3ms3988 KiB
26Wrong answer3ms3956 KiB
27Wrong answer3ms3964 KiB
28Wrong answer3ms4152 KiB
29Accepted3ms4144 KiB
30Wrong answer3ms4144 KiB
31Runtime error3ms4456 KiB
subtask40/20
32Accepted3ms2244 KiB
33Wrong answer3ms2444 KiB
34Runtime error3ms2760 KiB
35Wrong answer3ms2916 KiB
36Wrong answer3ms3088 KiB
37Wrong answer3ms3316 KiB
38Accepted2ms3196 KiB
39Wrong answer3ms3324 KiB
40Accepted2ms3420 KiB
41Accepted3ms3552 KiB
42Runtime error3ms3860 KiB
43Runtime error3ms3972 KiB
44Wrong answer3ms3988 KiB
45Wrong answer3ms3956 KiB
46Wrong answer3ms3964 KiB
47Wrong answer3ms4152 KiB
48Accepted3ms4144 KiB
49Wrong answer3ms4144 KiB
50Runtime error3ms4456 KiB
51Runtime error3ms4804 KiB
52Runtime error3ms4952 KiB
53Runtime error4ms5160 KiB
54Runtime error4ms5268 KiB
55Runtime error4ms5580 KiB
56Wrong answer3ms5676 KiB
57Wrong answer3ms5604 KiB
58Wrong answer3ms5520 KiB
59Wrong answer3ms5536 KiB
60Wrong answer3ms5440 KiB
61Runtime error3ms5528 KiB
62Wrong answer3ms5504 KiB
63Runtime error3ms5560 KiB
64Wrong answer3ms5736 KiB
65Wrong answer3ms5696 KiB
66Runtime error4ms5776 KiB
67Wrong answer3ms5688 KiB
68Wrong answer3ms5664 KiB
69Accepted4ms5660 KiB
70Wrong answer3ms5660 KiB
subtask50/40
71Accepted3ms2244 KiB
72Wrong answer3ms2444 KiB
73Runtime error3ms2760 KiB
74Wrong answer3ms2916 KiB
75Wrong answer3ms3088 KiB
76Wrong answer3ms3316 KiB
77Accepted2ms3196 KiB
78Wrong answer3ms3324 KiB
79Accepted2ms3420 KiB
80Accepted3ms3552 KiB
81Runtime error3ms3860 KiB
82Runtime error3ms3972 KiB
83Wrong answer3ms3988 KiB
84Wrong answer3ms3956 KiB
85Wrong answer3ms3964 KiB
86Wrong answer3ms4152 KiB
87Accepted3ms4144 KiB
88Wrong answer3ms4144 KiB
89Runtime error3ms4456 KiB
90Runtime error3ms4804 KiB
91Runtime error3ms4952 KiB
92Runtime error4ms5160 KiB
93Runtime error4ms5268 KiB
94Runtime error4ms5580 KiB
95Wrong answer3ms5676 KiB
96Wrong answer3ms5604 KiB
97Wrong answer3ms5520 KiB
98Wrong answer3ms5536 KiB
99Wrong answer3ms5440 KiB
100Runtime error3ms5528 KiB
101Wrong answer3ms5504 KiB
102Runtime error3ms5560 KiB
103Wrong answer3ms5736 KiB
104Wrong answer3ms5696 KiB
105Runtime error4ms5776 KiB
106Wrong answer3ms5688 KiB
107Wrong answer3ms5664 KiB
108Accepted4ms5660 KiB
109Wrong answer3ms5660 KiB
110Runtime error86ms29868 KiB
111Runtime error79ms29948 KiB
112Runtime error85ms29944 KiB
113Runtime error85ms29956 KiB
114Runtime error85ms29960 KiB
115Runtime error79ms30028 KiB
116Wrong answer87ms29952 KiB
117Wrong answer82ms30004 KiB
118Wrong answer86ms29980 KiB
119Wrong answer83ms29980 KiB
120Wrong answer86ms29976 KiB
121Wrong answer87ms30020 KiB
122Runtime error87ms29872 KiB
123Wrong answer86ms29872 KiB
124Runtime error83ms29968 KiB
125Wrong answer82ms29940 KiB
126Runtime error86ms29932 KiB
127Runtime error82ms30020 KiB
128Runtime error82ms29912 KiB
129Runtime error82ms29892 KiB
130Wrong answer81ms29976 KiB
131Accepted101ms29944 KiB
132Wrong answer82ms29940 KiB