109122024-04-18 20:21:22gortomiRajzcpp17Hibás válasz 0/10090ms29824 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(xb != xa)
    {
        long double b = (yb - ya) / (xb - xa);
        if(b == 0) return 0;
        long double x = xa + (-ya / b);
        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
1Elfogadva3ms1832 KiB
2Hibás válasz3ms2024 KiB
subtask20/20
3Elfogadva3ms2236 KiB
4Hibás válasz3ms2456 KiB
5Hibás válasz3ms2664 KiB
6Hibás válasz3ms2752 KiB
7Hibás válasz3ms2964 KiB
8Hibás válasz3ms2956 KiB
9Elfogadva3ms3052 KiB
10Hibás válasz3ms2952 KiB
11Elfogadva3ms3212 KiB
12Elfogadva3ms3300 KiB
subtask30/20
13Elfogadva3ms2236 KiB
14Hibás válasz3ms2456 KiB
15Hibás válasz3ms2664 KiB
16Hibás válasz3ms2752 KiB
17Hibás válasz3ms2964 KiB
18Hibás válasz3ms2956 KiB
19Elfogadva3ms3052 KiB
20Hibás válasz3ms2952 KiB
21Elfogadva3ms3212 KiB
22Elfogadva3ms3300 KiB
23Hibás válasz3ms3228 KiB
24Hibás válasz3ms3264 KiB
25Hibás válasz3ms3392 KiB
26Hibás válasz3ms3364 KiB
27Hibás válasz3ms3496 KiB
28Hibás válasz3ms3420 KiB
29Elfogadva3ms3512 KiB
30Hibás válasz3ms3604 KiB
31Elfogadva3ms3596 KiB
subtask40/20
32Elfogadva3ms2236 KiB
33Hibás válasz3ms2456 KiB
34Hibás válasz3ms2664 KiB
35Hibás válasz3ms2752 KiB
36Hibás válasz3ms2964 KiB
37Hibás válasz3ms2956 KiB
38Elfogadva3ms3052 KiB
39Hibás válasz3ms2952 KiB
40Elfogadva3ms3212 KiB
41Elfogadva3ms3300 KiB
42Hibás válasz3ms3228 KiB
43Hibás válasz3ms3264 KiB
44Hibás válasz3ms3392 KiB
45Hibás válasz3ms3364 KiB
46Hibás válasz3ms3496 KiB
47Hibás válasz3ms3420 KiB
48Elfogadva3ms3512 KiB
49Hibás válasz3ms3604 KiB
50Elfogadva3ms3596 KiB
51Hibás válasz3ms4204 KiB
52Hibás válasz3ms4232 KiB
53Hibás válasz3ms4232 KiB
54Hibás válasz3ms4520 KiB
55Hibás válasz3ms4768 KiB
56Hibás válasz3ms4640 KiB
57Hibás válasz3ms4596 KiB
58Hibás válasz3ms4576 KiB
59Hibás válasz4ms4824 KiB
60Hibás válasz3ms5012 KiB
61Hibás válasz3ms4864 KiB
62Hibás válasz3ms4880 KiB
63Hibás válasz3ms4904 KiB
64Hibás válasz3ms5176 KiB
65Hibás válasz3ms5128 KiB
66Hibás válasz3ms5132 KiB
67Hibás válasz3ms5032 KiB
68Hibás válasz3ms5048 KiB
69Elfogadva3ms5004 KiB
70Hibás válasz3ms5032 KiB
subtask50/40
71Elfogadva3ms2236 KiB
72Hibás válasz3ms2456 KiB
73Hibás válasz3ms2664 KiB
74Hibás válasz3ms2752 KiB
75Hibás válasz3ms2964 KiB
76Hibás válasz3ms2956 KiB
77Elfogadva3ms3052 KiB
78Hibás válasz3ms2952 KiB
79Elfogadva3ms3212 KiB
80Elfogadva3ms3300 KiB
81Hibás válasz3ms3228 KiB
82Hibás válasz3ms3264 KiB
83Hibás válasz3ms3392 KiB
84Hibás válasz3ms3364 KiB
85Hibás válasz3ms3496 KiB
86Hibás válasz3ms3420 KiB
87Elfogadva3ms3512 KiB
88Hibás válasz3ms3604 KiB
89Elfogadva3ms3596 KiB
90Hibás válasz3ms4204 KiB
91Hibás válasz3ms4232 KiB
92Hibás válasz3ms4232 KiB
93Hibás válasz3ms4520 KiB
94Hibás válasz3ms4768 KiB
95Hibás válasz3ms4640 KiB
96Hibás válasz3ms4596 KiB
97Hibás válasz3ms4576 KiB
98Hibás válasz4ms4824 KiB
99Hibás válasz3ms5012 KiB
100Hibás válasz3ms4864 KiB
101Hibás válasz3ms4880 KiB
102Hibás válasz3ms4904 KiB
103Hibás válasz3ms5176 KiB
104Hibás válasz3ms5128 KiB
105Hibás válasz3ms5132 KiB
106Hibás válasz3ms5032 KiB
107Hibás válasz3ms5048 KiB
108Elfogadva3ms5004 KiB
109Hibás válasz3ms5032 KiB
110Hibás válasz81ms29244 KiB
111Hibás válasz85ms29436 KiB
112Hibás válasz82ms29544 KiB
113Hibás válasz85ms29596 KiB
114Hibás válasz82ms29596 KiB
115Hibás válasz81ms29504 KiB
116Hibás válasz89ms29500 KiB
117Hibás válasz85ms29552 KiB
118Hibás válasz83ms29552 KiB
119Hibás válasz90ms29736 KiB
120Hibás válasz86ms29768 KiB
121Hibás válasz85ms29764 KiB
122Hibás válasz83ms29740 KiB
123Hibás válasz83ms29824 KiB
124Hibás válasz83ms29816 KiB
125Hibás válasz83ms29772 KiB
126Hibás válasz83ms29712 KiB
127Hibás válasz83ms29716 KiB
128Hibás válasz83ms29704 KiB
129Hibás válasz82ms29720 KiB
130Hibás válasz82ms29676 KiB
131Elfogadva79ms29732 KiB
132Hibás válasz83ms29680 KiB