109132024-04-18 20:27:00gortomiRajzcpp17Hibás válasz 0/10087ms29924 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)
    {
        double b = (yb - ya) / double(xb - xa);
        if(b == 0) return 0;
        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
1Elfogadva3ms1696 KiB
2Hibás válasz3ms1864 KiB
subtask20/20
3Hibás válasz3ms2080 KiB
4Hibás válasz3ms2300 KiB
5Hibás válasz3ms2516 KiB
6Hibás válasz3ms2720 KiB
7Hibás válasz3ms2932 KiB
8Hibás válasz3ms2992 KiB
9Elfogadva3ms3216 KiB
10Hibás válasz3ms3220 KiB
11Elfogadva3ms3300 KiB
12Elfogadva3ms3328 KiB
subtask30/20
13Hibás válasz3ms2080 KiB
14Hibás válasz3ms2300 KiB
15Hibás válasz3ms2516 KiB
16Hibás válasz3ms2720 KiB
17Hibás válasz3ms2932 KiB
18Hibás válasz3ms2992 KiB
19Elfogadva3ms3216 KiB
20Hibás válasz3ms3220 KiB
21Elfogadva3ms3300 KiB
22Elfogadva3ms3328 KiB
23Hibás válasz3ms3552 KiB
24Hibás válasz3ms3636 KiB
25Hibás válasz3ms3636 KiB
26Hibás válasz3ms3640 KiB
27Hibás válasz3ms3632 KiB
28Hibás válasz3ms3724 KiB
29Hibás válasz3ms3768 KiB
30Hibás válasz3ms3996 KiB
31Elfogadva2ms3948 KiB
subtask40/20
32Hibás válasz3ms2080 KiB
33Hibás válasz3ms2300 KiB
34Hibás válasz3ms2516 KiB
35Hibás válasz3ms2720 KiB
36Hibás válasz3ms2932 KiB
37Hibás válasz3ms2992 KiB
38Elfogadva3ms3216 KiB
39Hibás válasz3ms3220 KiB
40Elfogadva3ms3300 KiB
41Elfogadva3ms3328 KiB
42Hibás válasz3ms3552 KiB
43Hibás válasz3ms3636 KiB
44Hibás válasz3ms3636 KiB
45Hibás válasz3ms3640 KiB
46Hibás válasz3ms3632 KiB
47Hibás válasz3ms3724 KiB
48Hibás válasz3ms3768 KiB
49Hibás válasz3ms3996 KiB
50Elfogadva2ms3948 KiB
51Hibás válasz3ms4292 KiB
52Hibás válasz4ms4644 KiB
53Hibás válasz3ms4512 KiB
54Hibás válasz3ms4664 KiB
55Hibás válasz3ms4620 KiB
56Hibás válasz3ms4624 KiB
57Hibás válasz3ms4620 KiB
58Hibás válasz3ms4664 KiB
59Hibás válasz3ms4648 KiB
60Hibás válasz3ms4540 KiB
61Hibás válasz3ms4564 KiB
62Hibás válasz3ms4600 KiB
63Hibás válasz3ms4536 KiB
64Hibás válasz3ms4836 KiB
65Hibás válasz3ms5008 KiB
66Hibás válasz3ms5092 KiB
67Hibás válasz3ms5280 KiB
68Hibás válasz3ms5240 KiB
69Elfogadva3ms5240 KiB
70Hibás válasz3ms5240 KiB
subtask50/40
71Hibás válasz3ms2080 KiB
72Hibás válasz3ms2300 KiB
73Hibás válasz3ms2516 KiB
74Hibás válasz3ms2720 KiB
75Hibás válasz3ms2932 KiB
76Hibás válasz3ms2992 KiB
77Elfogadva3ms3216 KiB
78Hibás válasz3ms3220 KiB
79Elfogadva3ms3300 KiB
80Elfogadva3ms3328 KiB
81Hibás válasz3ms3552 KiB
82Hibás válasz3ms3636 KiB
83Hibás válasz3ms3636 KiB
84Hibás válasz3ms3640 KiB
85Hibás válasz3ms3632 KiB
86Hibás válasz3ms3724 KiB
87Hibás válasz3ms3768 KiB
88Hibás válasz3ms3996 KiB
89Elfogadva2ms3948 KiB
90Hibás válasz3ms4292 KiB
91Hibás válasz4ms4644 KiB
92Hibás válasz3ms4512 KiB
93Hibás válasz3ms4664 KiB
94Hibás válasz3ms4620 KiB
95Hibás válasz3ms4624 KiB
96Hibás válasz3ms4620 KiB
97Hibás válasz3ms4664 KiB
98Hibás válasz3ms4648 KiB
99Hibás válasz3ms4540 KiB
100Hibás válasz3ms4564 KiB
101Hibás válasz3ms4600 KiB
102Hibás válasz3ms4536 KiB
103Hibás válasz3ms4836 KiB
104Hibás válasz3ms5008 KiB
105Hibás válasz3ms5092 KiB
106Hibás válasz3ms5280 KiB
107Hibás válasz3ms5240 KiB
108Elfogadva3ms5240 KiB
109Hibás válasz3ms5240 KiB
110Hibás válasz86ms29476 KiB
111Hibás válasz81ms29452 KiB
112Hibás válasz85ms29504 KiB
113Hibás válasz85ms29548 KiB
114Hibás válasz86ms29580 KiB
115Hibás válasz85ms29636 KiB
116Hibás válasz83ms29684 KiB
117Hibás válasz83ms29704 KiB
118Hibás válasz82ms29712 KiB
119Hibás válasz87ms29644 KiB
120Hibás válasz83ms29644 KiB
121Hibás válasz83ms29644 KiB
122Hibás válasz87ms29692 KiB
123Hibás válasz83ms29692 KiB
124Hibás válasz82ms29640 KiB
125Hibás válasz87ms29704 KiB
126Hibás válasz86ms29652 KiB
127Hibás válasz82ms29708 KiB
128Hibás válasz86ms29660 KiB
129Hibás válasz82ms29704 KiB
130Hibás válasz86ms29884 KiB
131Elfogadva78ms29924 KiB
132Hibás válasz82ms29864 KiB