109142024-04-18 20:31:22gortomiRajzcpp17Hibás válasz 0/10089ms29780 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)
{
    if(ya == yb) return 0;
    if(xb != xa)
    {
        ll x = xa * (yb - ya) + -ya * (xb - xa);
        return x > 0;
    }
    return xa > 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Hibás válasz3ms2060 KiB
subtask20/20
3Hibás válasz3ms2268 KiB
4Hibás válasz3ms2316 KiB
5Hibás válasz3ms2444 KiB
6Hibás válasz3ms2676 KiB
7Hibás válasz3ms2888 KiB
8Hibás válasz3ms2976 KiB
9Hibás válasz3ms3072 KiB
10Hibás válasz3ms2980 KiB
11Elfogadva3ms3080 KiB
12Elfogadva3ms3208 KiB
subtask30/20
13Hibás válasz3ms2268 KiB
14Hibás válasz3ms2316 KiB
15Hibás válasz3ms2444 KiB
16Hibás válasz3ms2676 KiB
17Hibás válasz3ms2888 KiB
18Hibás válasz3ms2976 KiB
19Hibás válasz3ms3072 KiB
20Hibás válasz3ms2980 KiB
21Elfogadva3ms3080 KiB
22Elfogadva3ms3208 KiB
23Hibás válasz3ms3180 KiB
24Hibás válasz3ms3384 KiB
25Hibás válasz3ms3392 KiB
26Hibás válasz3ms3388 KiB
27Hibás válasz3ms3384 KiB
28Hibás válasz3ms3384 KiB
29Hibás válasz3ms3532 KiB
30Hibás válasz3ms3396 KiB
31Elfogadva3ms3384 KiB
subtask40/20
32Hibás válasz3ms2268 KiB
33Hibás válasz3ms2316 KiB
34Hibás válasz3ms2444 KiB
35Hibás válasz3ms2676 KiB
36Hibás válasz3ms2888 KiB
37Hibás válasz3ms2976 KiB
38Hibás válasz3ms3072 KiB
39Hibás válasz3ms2980 KiB
40Elfogadva3ms3080 KiB
41Elfogadva3ms3208 KiB
42Hibás válasz3ms3180 KiB
43Hibás válasz3ms3384 KiB
44Hibás válasz3ms3392 KiB
45Hibás válasz3ms3388 KiB
46Hibás válasz3ms3384 KiB
47Hibás válasz3ms3384 KiB
48Hibás válasz3ms3532 KiB
49Hibás válasz3ms3396 KiB
50Elfogadva3ms3384 KiB
51Hibás válasz3ms3844 KiB
52Hibás válasz3ms3848 KiB
53Hibás válasz3ms3848 KiB
54Hibás válasz3ms4120 KiB
55Hibás válasz3ms4388 KiB
56Hibás válasz3ms4272 KiB
57Hibás válasz3ms4292 KiB
58Hibás válasz3ms4308 KiB
59Hibás válasz3ms4300 KiB
60Hibás válasz3ms4304 KiB
61Hibás válasz3ms4552 KiB
62Hibás válasz3ms4512 KiB
63Hibás válasz3ms4772 KiB
64Hibás válasz3ms4772 KiB
65Hibás válasz3ms4720 KiB
66Hibás válasz3ms4724 KiB
67Hibás válasz3ms4720 KiB
68Hibás válasz3ms4716 KiB
69Hibás válasz3ms4968 KiB
70Hibás válasz3ms4984 KiB
subtask50/40
71Hibás válasz3ms2268 KiB
72Hibás válasz3ms2316 KiB
73Hibás válasz3ms2444 KiB
74Hibás válasz3ms2676 KiB
75Hibás válasz3ms2888 KiB
76Hibás válasz3ms2976 KiB
77Hibás válasz3ms3072 KiB
78Hibás válasz3ms2980 KiB
79Elfogadva3ms3080 KiB
80Elfogadva3ms3208 KiB
81Hibás válasz3ms3180 KiB
82Hibás válasz3ms3384 KiB
83Hibás válasz3ms3392 KiB
84Hibás válasz3ms3388 KiB
85Hibás válasz3ms3384 KiB
86Hibás válasz3ms3384 KiB
87Hibás válasz3ms3532 KiB
88Hibás válasz3ms3396 KiB
89Elfogadva3ms3384 KiB
90Hibás válasz3ms3844 KiB
91Hibás válasz3ms3848 KiB
92Hibás válasz3ms3848 KiB
93Hibás válasz3ms4120 KiB
94Hibás válasz3ms4388 KiB
95Hibás válasz3ms4272 KiB
96Hibás válasz3ms4292 KiB
97Hibás válasz3ms4308 KiB
98Hibás válasz3ms4300 KiB
99Hibás válasz3ms4304 KiB
100Hibás válasz3ms4552 KiB
101Hibás válasz3ms4512 KiB
102Hibás válasz3ms4772 KiB
103Hibás válasz3ms4772 KiB
104Hibás válasz3ms4720 KiB
105Hibás válasz3ms4724 KiB
106Hibás válasz3ms4720 KiB
107Hibás válasz3ms4716 KiB
108Hibás válasz3ms4968 KiB
109Hibás válasz3ms4984 KiB
110Hibás válasz86ms29144 KiB
111Hibás válasz86ms29152 KiB
112Hibás válasz85ms29172 KiB
113Hibás válasz85ms29204 KiB
114Hibás válasz86ms29196 KiB
115Hibás válasz85ms29200 KiB
116Hibás válasz89ms29152 KiB
117Hibás válasz85ms29312 KiB
118Hibás válasz87ms29492 KiB
119Hibás válasz89ms29496 KiB
120Hibás válasz89ms29496 KiB
121Hibás válasz86ms29444 KiB
122Hibás válasz89ms29612 KiB
123Hibás válasz87ms29576 KiB
124Hibás válasz87ms29572 KiB
125Hibás válasz87ms29508 KiB
126Hibás válasz87ms29516 KiB
127Hibás válasz87ms29512 KiB
128Hibás válasz87ms29484 KiB
129Hibás válasz83ms29780 KiB
130Hibás válasz87ms29720 KiB
131Hibás válasz68ms29652 KiB
132Hibás válasz87ms29540 KiB