109072024-04-18 19:53:07gortomiRajzcpp17Hibás válasz 0/10097ms29836 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)
{
    return 0;
    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
1Hibás válasz3ms1828 KiB
2Hibás válasz3ms2020 KiB
subtask20/20
3Hibás válasz3ms2104 KiB
4Hibás válasz3ms2340 KiB
5Hibás válasz3ms2456 KiB
6Hibás válasz3ms2684 KiB
7Hibás válasz3ms2900 KiB
8Hibás válasz3ms2980 KiB
9Hibás válasz3ms3388 KiB
10Hibás válasz3ms3572 KiB
11Elfogadva3ms3608 KiB
12Elfogadva3ms3532 KiB
subtask30/20
13Hibás válasz3ms2104 KiB
14Hibás válasz3ms2340 KiB
15Hibás válasz3ms2456 KiB
16Hibás válasz3ms2684 KiB
17Hibás válasz3ms2900 KiB
18Hibás válasz3ms2980 KiB
19Hibás válasz3ms3388 KiB
20Hibás válasz3ms3572 KiB
21Elfogadva3ms3608 KiB
22Elfogadva3ms3532 KiB
23Hibás válasz3ms3536 KiB
24Hibás válasz3ms3628 KiB
25Hibás válasz3ms3960 KiB
26Hibás válasz3ms4088 KiB
27Hibás válasz3ms4088 KiB
28Hibás válasz3ms3972 KiB
29Elfogadva3ms4104 KiB
30Elfogadva3ms4192 KiB
31Hibás válasz3ms4316 KiB
subtask40/20
32Hibás válasz3ms2104 KiB
33Hibás válasz3ms2340 KiB
34Hibás válasz3ms2456 KiB
35Hibás válasz3ms2684 KiB
36Hibás válasz3ms2900 KiB
37Hibás válasz3ms2980 KiB
38Hibás válasz3ms3388 KiB
39Hibás válasz3ms3572 KiB
40Elfogadva3ms3608 KiB
41Elfogadva3ms3532 KiB
42Hibás válasz3ms3536 KiB
43Hibás válasz3ms3628 KiB
44Hibás válasz3ms3960 KiB
45Hibás válasz3ms4088 KiB
46Hibás válasz3ms4088 KiB
47Hibás válasz3ms3972 KiB
48Elfogadva3ms4104 KiB
49Elfogadva3ms4192 KiB
50Hibás válasz3ms4316 KiB
51Hibás válasz4ms4764 KiB
52Hibás válasz3ms4768 KiB
53Hibás válasz4ms5048 KiB
54Hibás válasz3ms4996 KiB
55Hibás válasz3ms5120 KiB
56Hibás válasz3ms5392 KiB
57Hibás válasz4ms5344 KiB
58Hibás válasz3ms5632 KiB
59Hibás válasz3ms5500 KiB
60Hibás válasz3ms5504 KiB
61Hibás válasz3ms5448 KiB
62Hibás válasz3ms5452 KiB
63Hibás válasz4ms5572 KiB
64Hibás válasz3ms5580 KiB
65Hibás válasz3ms5584 KiB
66Hibás válasz4ms5536 KiB
67Elfogadva3ms5672 KiB
68Elfogadva3ms5576 KiB
69Elfogadva3ms5504 KiB
70Elfogadva3ms5532 KiB
subtask50/40
71Hibás válasz3ms2104 KiB
72Hibás válasz3ms2340 KiB
73Hibás válasz3ms2456 KiB
74Hibás válasz3ms2684 KiB
75Hibás válasz3ms2900 KiB
76Hibás válasz3ms2980 KiB
77Hibás válasz3ms3388 KiB
78Hibás válasz3ms3572 KiB
79Elfogadva3ms3608 KiB
80Elfogadva3ms3532 KiB
81Hibás válasz3ms3536 KiB
82Hibás válasz3ms3628 KiB
83Hibás válasz3ms3960 KiB
84Hibás válasz3ms4088 KiB
85Hibás válasz3ms4088 KiB
86Hibás válasz3ms3972 KiB
87Elfogadva3ms4104 KiB
88Elfogadva3ms4192 KiB
89Hibás válasz3ms4316 KiB
90Hibás válasz4ms4764 KiB
91Hibás válasz3ms4768 KiB
92Hibás válasz4ms5048 KiB
93Hibás válasz3ms4996 KiB
94Hibás válasz3ms5120 KiB
95Hibás válasz3ms5392 KiB
96Hibás válasz4ms5344 KiB
97Hibás válasz3ms5632 KiB
98Hibás válasz3ms5500 KiB
99Hibás válasz3ms5504 KiB
100Hibás válasz3ms5448 KiB
101Hibás válasz3ms5452 KiB
102Hibás válasz4ms5572 KiB
103Hibás válasz3ms5580 KiB
104Hibás válasz3ms5584 KiB
105Hibás válasz4ms5536 KiB
106Elfogadva3ms5672 KiB
107Elfogadva3ms5576 KiB
108Elfogadva3ms5504 KiB
109Elfogadva3ms5532 KiB
110Hibás válasz87ms29752 KiB
111Hibás válasz93ms29764 KiB
112Hibás válasz89ms29824 KiB
113Hibás válasz93ms29720 KiB
114Hibás válasz93ms29776 KiB
115Hibás válasz93ms29764 KiB
116Hibás válasz97ms29724 KiB
117Hibás válasz96ms29732 KiB
118Hibás válasz96ms29728 KiB
119Hibás válasz96ms29792 KiB
120Hibás válasz96ms29836 KiB
121Hibás válasz97ms29732 KiB
122Hibás válasz93ms29772 KiB
123Hibás válasz96ms29768 KiB
124Hibás válasz96ms29804 KiB
125Hibás válasz92ms29724 KiB
126Hibás válasz96ms29784 KiB
127Hibás válasz96ms29824 KiB
128Elfogadva94ms29820 KiB
129Hibás válasz90ms29820 KiB
130Hibás válasz94ms29780 KiB
131Elfogadva75ms29820 KiB
132Elfogadva96ms29836 KiB