109072024-04-18 19:53:07gortomiRajzcpp17Wrong answer 0/10097ms29836 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)
{
    return 0;
    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
1Wrong answer3ms1828 KiB
2Wrong answer3ms2020 KiB
subtask20/20
3Wrong answer3ms2104 KiB
4Wrong answer3ms2340 KiB
5Wrong answer3ms2456 KiB
6Wrong answer3ms2684 KiB
7Wrong answer3ms2900 KiB
8Wrong answer3ms2980 KiB
9Wrong answer3ms3388 KiB
10Wrong answer3ms3572 KiB
11Accepted3ms3608 KiB
12Accepted3ms3532 KiB
subtask30/20
13Wrong answer3ms2104 KiB
14Wrong answer3ms2340 KiB
15Wrong answer3ms2456 KiB
16Wrong answer3ms2684 KiB
17Wrong answer3ms2900 KiB
18Wrong answer3ms2980 KiB
19Wrong answer3ms3388 KiB
20Wrong answer3ms3572 KiB
21Accepted3ms3608 KiB
22Accepted3ms3532 KiB
23Wrong answer3ms3536 KiB
24Wrong answer3ms3628 KiB
25Wrong answer3ms3960 KiB
26Wrong answer3ms4088 KiB
27Wrong answer3ms4088 KiB
28Wrong answer3ms3972 KiB
29Accepted3ms4104 KiB
30Accepted3ms4192 KiB
31Wrong answer3ms4316 KiB
subtask40/20
32Wrong answer3ms2104 KiB
33Wrong answer3ms2340 KiB
34Wrong answer3ms2456 KiB
35Wrong answer3ms2684 KiB
36Wrong answer3ms2900 KiB
37Wrong answer3ms2980 KiB
38Wrong answer3ms3388 KiB
39Wrong answer3ms3572 KiB
40Accepted3ms3608 KiB
41Accepted3ms3532 KiB
42Wrong answer3ms3536 KiB
43Wrong answer3ms3628 KiB
44Wrong answer3ms3960 KiB
45Wrong answer3ms4088 KiB
46Wrong answer3ms4088 KiB
47Wrong answer3ms3972 KiB
48Accepted3ms4104 KiB
49Accepted3ms4192 KiB
50Wrong answer3ms4316 KiB
51Wrong answer4ms4764 KiB
52Wrong answer3ms4768 KiB
53Wrong answer4ms5048 KiB
54Wrong answer3ms4996 KiB
55Wrong answer3ms5120 KiB
56Wrong answer3ms5392 KiB
57Wrong answer4ms5344 KiB
58Wrong answer3ms5632 KiB
59Wrong answer3ms5500 KiB
60Wrong answer3ms5504 KiB
61Wrong answer3ms5448 KiB
62Wrong answer3ms5452 KiB
63Wrong answer4ms5572 KiB
64Wrong answer3ms5580 KiB
65Wrong answer3ms5584 KiB
66Wrong answer4ms5536 KiB
67Accepted3ms5672 KiB
68Accepted3ms5576 KiB
69Accepted3ms5504 KiB
70Accepted3ms5532 KiB
subtask50/40
71Wrong answer3ms2104 KiB
72Wrong answer3ms2340 KiB
73Wrong answer3ms2456 KiB
74Wrong answer3ms2684 KiB
75Wrong answer3ms2900 KiB
76Wrong answer3ms2980 KiB
77Wrong answer3ms3388 KiB
78Wrong answer3ms3572 KiB
79Accepted3ms3608 KiB
80Accepted3ms3532 KiB
81Wrong answer3ms3536 KiB
82Wrong answer3ms3628 KiB
83Wrong answer3ms3960 KiB
84Wrong answer3ms4088 KiB
85Wrong answer3ms4088 KiB
86Wrong answer3ms3972 KiB
87Accepted3ms4104 KiB
88Accepted3ms4192 KiB
89Wrong answer3ms4316 KiB
90Wrong answer4ms4764 KiB
91Wrong answer3ms4768 KiB
92Wrong answer4ms5048 KiB
93Wrong answer3ms4996 KiB
94Wrong answer3ms5120 KiB
95Wrong answer3ms5392 KiB
96Wrong answer4ms5344 KiB
97Wrong answer3ms5632 KiB
98Wrong answer3ms5500 KiB
99Wrong answer3ms5504 KiB
100Wrong answer3ms5448 KiB
101Wrong answer3ms5452 KiB
102Wrong answer4ms5572 KiB
103Wrong answer3ms5580 KiB
104Wrong answer3ms5584 KiB
105Wrong answer4ms5536 KiB
106Accepted3ms5672 KiB
107Accepted3ms5576 KiB
108Accepted3ms5504 KiB
109Accepted3ms5532 KiB
110Wrong answer87ms29752 KiB
111Wrong answer93ms29764 KiB
112Wrong answer89ms29824 KiB
113Wrong answer93ms29720 KiB
114Wrong answer93ms29776 KiB
115Wrong answer93ms29764 KiB
116Wrong answer97ms29724 KiB
117Wrong answer96ms29732 KiB
118Wrong answer96ms29728 KiB
119Wrong answer96ms29792 KiB
120Wrong answer96ms29836 KiB
121Wrong answer97ms29732 KiB
122Wrong answer93ms29772 KiB
123Wrong answer96ms29768 KiB
124Wrong answer96ms29804 KiB
125Wrong answer92ms29724 KiB
126Wrong answer96ms29784 KiB
127Wrong answer96ms29824 KiB
128Accepted94ms29820 KiB
129Wrong answer90ms29820 KiB
130Wrong answer94ms29780 KiB
131Accepted75ms29820 KiB
132Accepted96ms29836 KiB