109062024-04-18 19:52:37gortomiRajzcpp17Wrong answer 0/10089ms30020 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 1;
    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 answer3ms1956 KiB
subtask20/20
3Wrong answer3ms2168 KiB
4Wrong answer3ms2376 KiB
5Wrong answer3ms2600 KiB
6Wrong answer3ms2824 KiB
7Wrong answer3ms2884 KiB
8Wrong answer3ms2980 KiB
9Wrong answer3ms2976 KiB
10Wrong answer3ms3120 KiB
11Accepted3ms3232 KiB
12Accepted3ms3328 KiB
subtask30/20
13Wrong answer3ms2168 KiB
14Wrong answer3ms2376 KiB
15Wrong answer3ms2600 KiB
16Wrong answer3ms2824 KiB
17Wrong answer3ms2884 KiB
18Wrong answer3ms2980 KiB
19Wrong answer3ms2976 KiB
20Wrong answer3ms3120 KiB
21Accepted3ms3232 KiB
22Accepted3ms3328 KiB
23Wrong answer3ms3448 KiB
24Wrong answer3ms3664 KiB
25Wrong answer3ms3872 KiB
26Wrong answer3ms3960 KiB
27Wrong answer3ms3940 KiB
28Wrong answer3ms3936 KiB
29Wrong answer3ms3928 KiB
30Wrong answer3ms4016 KiB
31Wrong answer3ms3916 KiB
subtask40/20
32Wrong answer3ms2168 KiB
33Wrong answer3ms2376 KiB
34Wrong answer3ms2600 KiB
35Wrong answer3ms2824 KiB
36Wrong answer3ms2884 KiB
37Wrong answer3ms2980 KiB
38Wrong answer3ms2976 KiB
39Wrong answer3ms3120 KiB
40Accepted3ms3232 KiB
41Accepted3ms3328 KiB
42Wrong answer3ms3448 KiB
43Wrong answer3ms3664 KiB
44Wrong answer3ms3872 KiB
45Wrong answer3ms3960 KiB
46Wrong answer3ms3940 KiB
47Wrong answer3ms3936 KiB
48Wrong answer3ms3928 KiB
49Wrong answer3ms4016 KiB
50Wrong answer3ms3916 KiB
51Wrong answer3ms4200 KiB
52Wrong answer3ms4476 KiB
53Wrong answer3ms4440 KiB
54Wrong answer3ms4580 KiB
55Wrong answer3ms4520 KiB
56Wrong answer3ms4516 KiB
57Wrong answer3ms4444 KiB
58Wrong answer3ms4464 KiB
59Wrong answer3ms4444 KiB
60Wrong answer3ms4440 KiB
61Wrong answer3ms4484 KiB
62Wrong answer3ms4472 KiB
63Wrong answer3ms4728 KiB
64Wrong answer3ms5020 KiB
65Wrong answer3ms4868 KiB
66Wrong answer3ms5148 KiB
67Wrong answer3ms5076 KiB
68Wrong answer3ms5108 KiB
69Wrong answer3ms5304 KiB
70Wrong answer3ms5360 KiB
subtask50/40
71Wrong answer3ms2168 KiB
72Wrong answer3ms2376 KiB
73Wrong answer3ms2600 KiB
74Wrong answer3ms2824 KiB
75Wrong answer3ms2884 KiB
76Wrong answer3ms2980 KiB
77Wrong answer3ms2976 KiB
78Wrong answer3ms3120 KiB
79Accepted3ms3232 KiB
80Accepted3ms3328 KiB
81Wrong answer3ms3448 KiB
82Wrong answer3ms3664 KiB
83Wrong answer3ms3872 KiB
84Wrong answer3ms3960 KiB
85Wrong answer3ms3940 KiB
86Wrong answer3ms3936 KiB
87Wrong answer3ms3928 KiB
88Wrong answer3ms4016 KiB
89Wrong answer3ms3916 KiB
90Wrong answer3ms4200 KiB
91Wrong answer3ms4476 KiB
92Wrong answer3ms4440 KiB
93Wrong answer3ms4580 KiB
94Wrong answer3ms4520 KiB
95Wrong answer3ms4516 KiB
96Wrong answer3ms4444 KiB
97Wrong answer3ms4464 KiB
98Wrong answer3ms4444 KiB
99Wrong answer3ms4440 KiB
100Wrong answer3ms4484 KiB
101Wrong answer3ms4472 KiB
102Wrong answer3ms4728 KiB
103Wrong answer3ms5020 KiB
104Wrong answer3ms4868 KiB
105Wrong answer3ms5148 KiB
106Wrong answer3ms5076 KiB
107Wrong answer3ms5108 KiB
108Wrong answer3ms5304 KiB
109Wrong answer3ms5360 KiB
110Wrong answer86ms29484 KiB
111Wrong answer86ms29456 KiB
112Wrong answer85ms29452 KiB
113Wrong answer85ms29456 KiB
114Wrong answer86ms29504 KiB
115Wrong answer85ms29452 KiB
116Wrong answer87ms29456 KiB
117Wrong answer89ms29460 KiB
118Wrong answer87ms29516 KiB
119Wrong answer89ms29596 KiB
120Wrong answer89ms29668 KiB
121Wrong answer89ms29672 KiB
122Wrong answer89ms29684 KiB
123Wrong answer85ms29840 KiB
124Wrong answer87ms29784 KiB
125Wrong answer87ms29788 KiB
126Wrong answer87ms29712 KiB
127Wrong answer83ms29668 KiB
128Wrong answer87ms29840 KiB
129Wrong answer86ms30020 KiB
130Wrong answer83ms29936 KiB
131Wrong answer68ms29924 KiB
132Wrong answer83ms29920 KiB