109032024-04-18 19:38:27gortomiRajzcpp17Hibás válasz 0/10089ms29988 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> p, r;
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)
{
    long double b = (yb - ya) / (xb - xa);
    if(abs(b) < 1e-10) return 0;
    long double x = xa + (-ya / b);
    return x > 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    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)
    {
        //cout << a << " " << b << " " << d << "\n";
        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
1Elfogadva3ms1824 KiB
2Hibás válasz3ms2064 KiB
subtask20/20
3Elfogadva3ms2236 KiB
4Hibás válasz3ms2460 KiB
5Futási hiba3ms2784 KiB
6Hibás válasz3ms2904 KiB
7Hibás válasz3ms3016 KiB
8Hibás válasz3ms3368 KiB
9Elfogadva3ms3376 KiB
10Hibás válasz3ms3364 KiB
11Elfogadva3ms3304 KiB
12Elfogadva3ms3300 KiB
subtask30/20
13Elfogadva3ms2236 KiB
14Hibás válasz3ms2460 KiB
15Futási hiba3ms2784 KiB
16Hibás válasz3ms2904 KiB
17Hibás válasz3ms3016 KiB
18Hibás válasz3ms3368 KiB
19Elfogadva3ms3376 KiB
20Hibás válasz3ms3364 KiB
21Elfogadva3ms3304 KiB
22Elfogadva3ms3300 KiB
23Futási hiba3ms3640 KiB
24Futási hiba3ms3724 KiB
25Hibás válasz3ms3704 KiB
26Hibás válasz3ms3928 KiB
27Hibás válasz3ms3924 KiB
28Hibás válasz3ms3924 KiB
29Elfogadva3ms3988 KiB
30Hibás válasz3ms4124 KiB
31Futási hiba3ms4088 KiB
subtask40/20
32Elfogadva3ms2236 KiB
33Hibás válasz3ms2460 KiB
34Futási hiba3ms2784 KiB
35Hibás válasz3ms2904 KiB
36Hibás válasz3ms3016 KiB
37Hibás válasz3ms3368 KiB
38Elfogadva3ms3376 KiB
39Hibás válasz3ms3364 KiB
40Elfogadva3ms3304 KiB
41Elfogadva3ms3300 KiB
42Futási hiba3ms3640 KiB
43Futási hiba3ms3724 KiB
44Hibás válasz3ms3704 KiB
45Hibás válasz3ms3928 KiB
46Hibás válasz3ms3924 KiB
47Hibás válasz3ms3924 KiB
48Elfogadva3ms3988 KiB
49Hibás válasz3ms4124 KiB
50Futási hiba3ms4088 KiB
51Futási hiba3ms4660 KiB
52Futási hiba3ms4660 KiB
53Futási hiba4ms4980 KiB
54Futási hiba4ms4936 KiB
55Futási hiba3ms4884 KiB
56Hibás válasz3ms4856 KiB
57Hibás válasz3ms4856 KiB
58Hibás válasz3ms4800 KiB
59Hibás válasz3ms4796 KiB
60Hibás válasz3ms4832 KiB
61Futási hiba3ms4912 KiB
62Hibás válasz3ms4856 KiB
63Futási hiba3ms4940 KiB
64Hibás válasz3ms4912 KiB
65Hibás válasz3ms4916 KiB
66Futási hiba3ms4964 KiB
67Hibás válasz3ms4972 KiB
68Hibás válasz4ms5212 KiB
69Elfogadva3ms5132 KiB
70Hibás válasz3ms5336 KiB
subtask50/40
71Elfogadva3ms2236 KiB
72Hibás válasz3ms2460 KiB
73Futási hiba3ms2784 KiB
74Hibás válasz3ms2904 KiB
75Hibás válasz3ms3016 KiB
76Hibás válasz3ms3368 KiB
77Elfogadva3ms3376 KiB
78Hibás válasz3ms3364 KiB
79Elfogadva3ms3304 KiB
80Elfogadva3ms3300 KiB
81Futási hiba3ms3640 KiB
82Futási hiba3ms3724 KiB
83Hibás válasz3ms3704 KiB
84Hibás válasz3ms3928 KiB
85Hibás válasz3ms3924 KiB
86Hibás válasz3ms3924 KiB
87Elfogadva3ms3988 KiB
88Hibás válasz3ms4124 KiB
89Futási hiba3ms4088 KiB
90Futási hiba3ms4660 KiB
91Futási hiba3ms4660 KiB
92Futási hiba4ms4980 KiB
93Futási hiba4ms4936 KiB
94Futási hiba3ms4884 KiB
95Hibás válasz3ms4856 KiB
96Hibás válasz3ms4856 KiB
97Hibás válasz3ms4800 KiB
98Hibás válasz3ms4796 KiB
99Hibás válasz3ms4832 KiB
100Futási hiba3ms4912 KiB
101Hibás válasz3ms4856 KiB
102Futási hiba3ms4940 KiB
103Hibás válasz3ms4912 KiB
104Hibás válasz3ms4916 KiB
105Futási hiba3ms4964 KiB
106Hibás válasz3ms4972 KiB
107Hibás válasz4ms5212 KiB
108Elfogadva3ms5132 KiB
109Hibás válasz3ms5336 KiB
110Futási hiba79ms29456 KiB
111Futási hiba86ms29516 KiB
112Futási hiba81ms29560 KiB
113Futási hiba79ms29524 KiB
114Futási hiba86ms29528 KiB
115Futási hiba86ms29648 KiB
116Hibás válasz82ms29792 KiB
117Hibás válasz82ms29788 KiB
118Hibás válasz86ms29840 KiB
119Hibás válasz83ms29884 KiB
120Hibás válasz87ms29880 KiB
121Hibás válasz89ms29940 KiB
122Futási hiba83ms29876 KiB
123Hibás válasz82ms29880 KiB
124Futási hiba82ms29876 KiB
125Hibás válasz82ms29872 KiB
126Futási hiba82ms29876 KiB
127Futási hiba82ms29884 KiB
128Futási hiba82ms29948 KiB
129Futási hiba82ms29948 KiB
130Hibás válasz82ms29988 KiB
131Elfogadva79ms29872 KiB
132Hibás válasz82ms29872 KiB