109022024-04-18 19:30:14gortomiRajzcpp17Wrong answer 0/10083ms29876 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(b == 0) 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
1Accepted3ms1976 KiB
2Wrong answer3ms2128 KiB
subtask20/20
3Accepted3ms2248 KiB
4Wrong answer3ms2468 KiB
5Runtime error3ms2656 KiB
6Wrong answer3ms2808 KiB
7Wrong answer3ms2892 KiB
8Wrong answer3ms2816 KiB
9Accepted3ms2908 KiB
10Wrong answer3ms3044 KiB
11Accepted3ms3264 KiB
12Accepted3ms3328 KiB
subtask30/20
13Accepted3ms2248 KiB
14Wrong answer3ms2468 KiB
15Runtime error3ms2656 KiB
16Wrong answer3ms2808 KiB
17Wrong answer3ms2892 KiB
18Wrong answer3ms2816 KiB
19Accepted3ms2908 KiB
20Wrong answer3ms3044 KiB
21Accepted3ms3264 KiB
22Accepted3ms3328 KiB
23Runtime error3ms3576 KiB
24Runtime error3ms3784 KiB
25Wrong answer3ms3772 KiB
26Wrong answer3ms3800 KiB
27Wrong answer3ms3880 KiB
28Wrong answer3ms3976 KiB
29Accepted3ms3976 KiB
30Wrong answer3ms4116 KiB
31Runtime error3ms4136 KiB
subtask40/20
32Accepted3ms2248 KiB
33Wrong answer3ms2468 KiB
34Runtime error3ms2656 KiB
35Wrong answer3ms2808 KiB
36Wrong answer3ms2892 KiB
37Wrong answer3ms2816 KiB
38Accepted3ms2908 KiB
39Wrong answer3ms3044 KiB
40Accepted3ms3264 KiB
41Accepted3ms3328 KiB
42Runtime error3ms3576 KiB
43Runtime error3ms3784 KiB
44Wrong answer3ms3772 KiB
45Wrong answer3ms3800 KiB
46Wrong answer3ms3880 KiB
47Wrong answer3ms3976 KiB
48Accepted3ms3976 KiB
49Wrong answer3ms4116 KiB
50Runtime error3ms4136 KiB
51Runtime error3ms4624 KiB
52Runtime error4ms4944 KiB
53Runtime error4ms5152 KiB
54Runtime error4ms5148 KiB
55Runtime error4ms5200 KiB
56Wrong answer3ms4960 KiB
57Wrong answer3ms4988 KiB
58Wrong answer3ms5008 KiB
59Wrong answer3ms5020 KiB
60Wrong answer3ms5004 KiB
61Runtime error3ms5072 KiB
62Wrong answer3ms5036 KiB
63Runtime error4ms5352 KiB
64Wrong answer3ms5272 KiB
65Wrong answer3ms5296 KiB
66Runtime error3ms5252 KiB
67Wrong answer3ms5308 KiB
68Wrong answer3ms5280 KiB
69Accepted4ms5196 KiB
70Wrong answer3ms5200 KiB
subtask50/40
71Accepted3ms2248 KiB
72Wrong answer3ms2468 KiB
73Runtime error3ms2656 KiB
74Wrong answer3ms2808 KiB
75Wrong answer3ms2892 KiB
76Wrong answer3ms2816 KiB
77Accepted3ms2908 KiB
78Wrong answer3ms3044 KiB
79Accepted3ms3264 KiB
80Accepted3ms3328 KiB
81Runtime error3ms3576 KiB
82Runtime error3ms3784 KiB
83Wrong answer3ms3772 KiB
84Wrong answer3ms3800 KiB
85Wrong answer3ms3880 KiB
86Wrong answer3ms3976 KiB
87Accepted3ms3976 KiB
88Wrong answer3ms4116 KiB
89Runtime error3ms4136 KiB
90Runtime error3ms4624 KiB
91Runtime error4ms4944 KiB
92Runtime error4ms5152 KiB
93Runtime error4ms5148 KiB
94Runtime error4ms5200 KiB
95Wrong answer3ms4960 KiB
96Wrong answer3ms4988 KiB
97Wrong answer3ms5008 KiB
98Wrong answer3ms5020 KiB
99Wrong answer3ms5004 KiB
100Runtime error3ms5072 KiB
101Wrong answer3ms5036 KiB
102Runtime error4ms5352 KiB
103Wrong answer3ms5272 KiB
104Wrong answer3ms5296 KiB
105Runtime error3ms5252 KiB
106Wrong answer3ms5308 KiB
107Wrong answer3ms5280 KiB
108Accepted4ms5196 KiB
109Wrong answer3ms5200 KiB
110Runtime error81ms29532 KiB
111Runtime error79ms29624 KiB
112Runtime error79ms29640 KiB
113Runtime error79ms29644 KiB
114Runtime error81ms29620 KiB
115Runtime error79ms29624 KiB
116Wrong answer82ms29628 KiB
117Wrong answer82ms29672 KiB
118Wrong answer82ms29672 KiB
119Wrong answer82ms29692 KiB
120Wrong answer82ms29700 KiB
121Wrong answer83ms29700 KiB
122Runtime error82ms29752 KiB
123Wrong answer82ms29720 KiB
124Runtime error82ms29876 KiB
125Wrong answer82ms29788 KiB
126Runtime error82ms29628 KiB
127Runtime error82ms29708 KiB
128Runtime error82ms29708 KiB
129Runtime error82ms29628 KiB
130Wrong answer82ms29708 KiB
131Accepted79ms29756 KiB
132Wrong answer82ms29712 KiB