109032024-04-18 19:38:27gortomiRajzcpp17Wrong answer 0/10089ms29988 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
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(abs(b) < 1e-10) return 0;
    long double x = xa + (-ya / b);
    return x > 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    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)
    {
        //cout << a << " " << b << " " << d << "\n";
        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
1Accepted3ms1824 KiB
2Wrong answer3ms2064 KiB
subtask20/20
3Accepted3ms2236 KiB
4Wrong answer3ms2460 KiB
5Runtime error3ms2784 KiB
6Wrong answer3ms2904 KiB
7Wrong answer3ms3016 KiB
8Wrong answer3ms3368 KiB
9Accepted3ms3376 KiB
10Wrong answer3ms3364 KiB
11Accepted3ms3304 KiB
12Accepted3ms3300 KiB
subtask30/20
13Accepted3ms2236 KiB
14Wrong answer3ms2460 KiB
15Runtime error3ms2784 KiB
16Wrong answer3ms2904 KiB
17Wrong answer3ms3016 KiB
18Wrong answer3ms3368 KiB
19Accepted3ms3376 KiB
20Wrong answer3ms3364 KiB
21Accepted3ms3304 KiB
22Accepted3ms3300 KiB
23Runtime error3ms3640 KiB
24Runtime error3ms3724 KiB
25Wrong answer3ms3704 KiB
26Wrong answer3ms3928 KiB
27Wrong answer3ms3924 KiB
28Wrong answer3ms3924 KiB
29Accepted3ms3988 KiB
30Wrong answer3ms4124 KiB
31Runtime error3ms4088 KiB
subtask40/20
32Accepted3ms2236 KiB
33Wrong answer3ms2460 KiB
34Runtime error3ms2784 KiB
35Wrong answer3ms2904 KiB
36Wrong answer3ms3016 KiB
37Wrong answer3ms3368 KiB
38Accepted3ms3376 KiB
39Wrong answer3ms3364 KiB
40Accepted3ms3304 KiB
41Accepted3ms3300 KiB
42Runtime error3ms3640 KiB
43Runtime error3ms3724 KiB
44Wrong answer3ms3704 KiB
45Wrong answer3ms3928 KiB
46Wrong answer3ms3924 KiB
47Wrong answer3ms3924 KiB
48Accepted3ms3988 KiB
49Wrong answer3ms4124 KiB
50Runtime error3ms4088 KiB
51Runtime error3ms4660 KiB
52Runtime error3ms4660 KiB
53Runtime error4ms4980 KiB
54Runtime error4ms4936 KiB
55Runtime error3ms4884 KiB
56Wrong answer3ms4856 KiB
57Wrong answer3ms4856 KiB
58Wrong answer3ms4800 KiB
59Wrong answer3ms4796 KiB
60Wrong answer3ms4832 KiB
61Runtime error3ms4912 KiB
62Wrong answer3ms4856 KiB
63Runtime error3ms4940 KiB
64Wrong answer3ms4912 KiB
65Wrong answer3ms4916 KiB
66Runtime error3ms4964 KiB
67Wrong answer3ms4972 KiB
68Wrong answer4ms5212 KiB
69Accepted3ms5132 KiB
70Wrong answer3ms5336 KiB
subtask50/40
71Accepted3ms2236 KiB
72Wrong answer3ms2460 KiB
73Runtime error3ms2784 KiB
74Wrong answer3ms2904 KiB
75Wrong answer3ms3016 KiB
76Wrong answer3ms3368 KiB
77Accepted3ms3376 KiB
78Wrong answer3ms3364 KiB
79Accepted3ms3304 KiB
80Accepted3ms3300 KiB
81Runtime error3ms3640 KiB
82Runtime error3ms3724 KiB
83Wrong answer3ms3704 KiB
84Wrong answer3ms3928 KiB
85Wrong answer3ms3924 KiB
86Wrong answer3ms3924 KiB
87Accepted3ms3988 KiB
88Wrong answer3ms4124 KiB
89Runtime error3ms4088 KiB
90Runtime error3ms4660 KiB
91Runtime error3ms4660 KiB
92Runtime error4ms4980 KiB
93Runtime error4ms4936 KiB
94Runtime error3ms4884 KiB
95Wrong answer3ms4856 KiB
96Wrong answer3ms4856 KiB
97Wrong answer3ms4800 KiB
98Wrong answer3ms4796 KiB
99Wrong answer3ms4832 KiB
100Runtime error3ms4912 KiB
101Wrong answer3ms4856 KiB
102Runtime error3ms4940 KiB
103Wrong answer3ms4912 KiB
104Wrong answer3ms4916 KiB
105Runtime error3ms4964 KiB
106Wrong answer3ms4972 KiB
107Wrong answer4ms5212 KiB
108Accepted3ms5132 KiB
109Wrong answer3ms5336 KiB
110Runtime error79ms29456 KiB
111Runtime error86ms29516 KiB
112Runtime error81ms29560 KiB
113Runtime error79ms29524 KiB
114Runtime error86ms29528 KiB
115Runtime error86ms29648 KiB
116Wrong answer82ms29792 KiB
117Wrong answer82ms29788 KiB
118Wrong answer86ms29840 KiB
119Wrong answer83ms29884 KiB
120Wrong answer87ms29880 KiB
121Wrong answer89ms29940 KiB
122Runtime error83ms29876 KiB
123Wrong answer82ms29880 KiB
124Runtime error82ms29876 KiB
125Wrong answer82ms29872 KiB
126Runtime error82ms29876 KiB
127Runtime error82ms29884 KiB
128Runtime error82ms29948 KiB
129Runtime error82ms29948 KiB
130Wrong answer82ms29988 KiB
131Accepted79ms29872 KiB
132Wrong answer82ms29872 KiB