109042024-04-18 19:48:56gortomiRajzcpp17Hibás válasz 0/100101ms29920 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
int n;
int get(int v)
{
    if(v > 2 * n || v <= 0) cout << "-1" << endl;
    return p[v] == 0 ? v : p[v] = get(p[v]);
}
void unio(int a, int b)
{
    a = get(a);
    b = get(b);
    if(a > 2 * n || b > 2 * n || a == 0 || b == 0) cout << "-1" << endl;
    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)
{
    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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1828 KiB
2Hibás válasz3ms2064 KiB
subtask20/20
3Elfogadva3ms2516 KiB
4Hibás válasz3ms2520 KiB
5Futási hiba3ms2848 KiB
6Hibás válasz3ms2788 KiB
7Hibás válasz3ms2848 KiB
8Hibás válasz3ms3036 KiB
9Elfogadva3ms3244 KiB
10Hibás válasz3ms3592 KiB
11Elfogadva3ms3452 KiB
12Elfogadva3ms3572 KiB
subtask30/20
13Elfogadva3ms2516 KiB
14Hibás válasz3ms2520 KiB
15Futási hiba3ms2848 KiB
16Hibás válasz3ms2788 KiB
17Hibás válasz3ms2848 KiB
18Hibás válasz3ms3036 KiB
19Elfogadva3ms3244 KiB
20Hibás válasz3ms3592 KiB
21Elfogadva3ms3452 KiB
22Elfogadva3ms3572 KiB
23Futási hiba3ms3684 KiB
24Futási hiba3ms3928 KiB
25Hibás válasz3ms3940 KiB
26Hibás válasz3ms4004 KiB
27Hibás válasz3ms4072 KiB
28Hibás válasz3ms4136 KiB
29Elfogadva3ms4208 KiB
30Hibás válasz3ms4212 KiB
31Futási hiba3ms4168 KiB
subtask40/20
32Elfogadva3ms2516 KiB
33Hibás válasz3ms2520 KiB
34Futási hiba3ms2848 KiB
35Hibás válasz3ms2788 KiB
36Hibás válasz3ms2848 KiB
37Hibás válasz3ms3036 KiB
38Elfogadva3ms3244 KiB
39Hibás válasz3ms3592 KiB
40Elfogadva3ms3452 KiB
41Elfogadva3ms3572 KiB
42Futási hiba3ms3684 KiB
43Futási hiba3ms3928 KiB
44Hibás válasz3ms3940 KiB
45Hibás válasz3ms4004 KiB
46Hibás válasz3ms4072 KiB
47Hibás válasz3ms4136 KiB
48Elfogadva3ms4208 KiB
49Hibás válasz3ms4212 KiB
50Futási hiba3ms4168 KiB
51Futási hiba3ms4740 KiB
52Futási hiba4ms5060 KiB
53Futási hiba4ms4868 KiB
54Futási hiba4ms5068 KiB
55Futási hiba3ms5108 KiB
56Hibás válasz4ms4892 KiB
57Hibás válasz3ms4812 KiB
58Hibás válasz3ms4836 KiB
59Hibás válasz3ms4812 KiB
60Hibás válasz3ms4816 KiB
61Futási hiba4ms5416 KiB
62Hibás válasz3ms5528 KiB
63Futási hiba3ms5564 KiB
64Hibás válasz3ms5492 KiB
65Hibás válasz3ms5524 KiB
66Futási hiba3ms5552 KiB
67Hibás válasz3ms5376 KiB
68Hibás válasz3ms5660 KiB
69Elfogadva3ms5652 KiB
70Hibás válasz3ms5592 KiB
subtask50/40
71Elfogadva3ms2516 KiB
72Hibás válasz3ms2520 KiB
73Futási hiba3ms2848 KiB
74Hibás válasz3ms2788 KiB
75Hibás válasz3ms2848 KiB
76Hibás válasz3ms3036 KiB
77Elfogadva3ms3244 KiB
78Hibás válasz3ms3592 KiB
79Elfogadva3ms3452 KiB
80Elfogadva3ms3572 KiB
81Futási hiba3ms3684 KiB
82Futási hiba3ms3928 KiB
83Hibás válasz3ms3940 KiB
84Hibás válasz3ms4004 KiB
85Hibás válasz3ms4072 KiB
86Hibás válasz3ms4136 KiB
87Elfogadva3ms4208 KiB
88Hibás válasz3ms4212 KiB
89Futási hiba3ms4168 KiB
90Futási hiba3ms4740 KiB
91Futási hiba4ms5060 KiB
92Futási hiba4ms4868 KiB
93Futási hiba4ms5068 KiB
94Futási hiba3ms5108 KiB
95Hibás válasz4ms4892 KiB
96Hibás válasz3ms4812 KiB
97Hibás válasz3ms4836 KiB
98Hibás válasz3ms4812 KiB
99Hibás válasz3ms4816 KiB
100Futási hiba4ms5416 KiB
101Hibás válasz3ms5528 KiB
102Futási hiba3ms5564 KiB
103Hibás válasz3ms5492 KiB
104Hibás válasz3ms5524 KiB
105Futási hiba3ms5552 KiB
106Hibás válasz3ms5376 KiB
107Hibás válasz3ms5660 KiB
108Elfogadva3ms5652 KiB
109Hibás válasz3ms5592 KiB
110Futási hiba79ms29828 KiB
111Futási hiba79ms29920 KiB
112Futási hiba79ms29776 KiB
113Futási hiba79ms29780 KiB
114Futási hiba79ms29704 KiB
115Futási hiba79ms29808 KiB
116Hibás válasz82ms29784 KiB
117Hibás válasz82ms29840 KiB
118Hibás válasz82ms29820 KiB
119Hibás válasz82ms29688 KiB
120Hibás válasz82ms29680 KiB
121Hibás válasz82ms29684 KiB
122Futási hiba82ms29684 KiB
123Hibás válasz82ms29760 KiB
124Futási hiba82ms29704 KiB
125Hibás válasz82ms29812 KiB
126Futási hiba81ms29684 KiB
127Futási hiba82ms29688 KiB
128Futási hiba82ms29680 KiB
129Futási hiba81ms29772 KiB
130Hibás válasz81ms29868 KiB
131Elfogadva101ms29864 KiB
132Hibás válasz82ms29680 KiB