5397 2023. 05. 10 18:27:05 mraron Rajz cpp17 Time limit exceeded 60/100 1.082s 8856 KiB 
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

struct point{
    long long x, y;
    point(long long x = 0, long long y = 0) : x(x), y(y) {}
    point operator-() const { return point(-x, -y); }
    point operator+(point p) const { return point(x + p.x, y + p.y); }
    point operator-(point p) const { return (*this) + (-p); }
    long long len() const { return x*x + y*y; }
};

inline long long cross(point a, point b) { return a.x * b.y - b.x * a.y; }

inline int sgn(long long x) { return (x > 0) - (x < 0); }

inline int dir(point a, point b, point c) { return sgn(cross(b-a, c-a)); }

inline bool contains(point a, point b, point c, point d){
    int d1 = dir(a, b, d);
    int d2 = dir(b, c, d);
    int d3 = dir(c, a, d);
    return d1 == d2 && d2 == d3;
}

vector<vector<int>> g;
vector<bool> vis, done;
vector<point> v;

void add_edge(int x, int y){
    if(dir(v[x], v[y], point(0, 0)) > 0) g[x].push_back(y);
    else g[y].push_back(x);
}

bool dfs(int x){
    vis[x] = true;
    for(int y : g[x]){
        if((vis[y] && !done[y]) || (!vis[y] && dfs(y))) return true;
    }
    done[x] = true;
    return false;
}

const long long INF = 8e18 + 1;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin>>n;

    v.resize(n);
    for(auto &[x, y] : v) cin>>x>>y;

    long long lo = 0, hi = INF;
    while(lo + 1 < hi){
        long long mid = lo + (hi - lo) / 2;
        deque<pair<int, int>> q;
        vector<vector<bool>> used(n, vector<bool>(n));
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                if((v[i]-v[j]).len() <= mid){
                    q.emplace_back(i, j);
                    used[i][j] = used[j][i] = true;
                }
            }
        }
        g.assign(n, vector<int>());
        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop_front();
            add_edge(x, y);
            for(int i = 0; i < n; i++){
                if(i == x || i == y || contains(v[x], v[y], v[i], point(0, 0))) continue;
                if(used[x][i] && !used[y][i]) {
                    q.emplace_back(y, i);
                    used[y][i] = used[i][y] = true;
                }
                if(!used[x][i] && used[y][i]) {
                    q.emplace_back(x, i);
                    used[x][i] = used[i][x] = true;
                }
            }
        }
        vis.assign(n, false);
        done.assign(n, false);
        bool ok = false;
        for(int i = 0; i < n; i++){
            if(!vis[i]){
                ok = ok || dfs(i);
            }
        }
        if(ok) hi = mid;
        else lo = mid;
    }

    if(hi == INF) cout<<-1<<'\n';
    else cout<<hi<<'\n';

    return 0;
}
Subtask Sum Test Verdict Time Memory
subtask1 0/0
1 Accepted 3ms 1828 KiB
2 Accepted 3ms 2032 KiB
subtask2 20/20
3 Accepted 3ms 2032 KiB
4 Accepted 3ms 2260 KiB
5 Accepted 3ms 2328 KiB
6 Accepted 3ms 2460 KiB
7 Accepted 3ms 2672 KiB
8 Accepted 3ms 2756 KiB
9 Accepted 3ms 2980 KiB
10 Accepted 3ms 2988 KiB
11 Accepted 3ms 2968 KiB
12 Accepted 3ms 2964 KiB
13 Accepted 3ms 3096 KiB
subtask3 20/20
14 Accepted 3ms 3096 KiB
15 Accepted 3ms 2260 KiB
16 Accepted 3ms 2328 KiB
17 Accepted 3ms 2460 KiB
18 Accepted 3ms 2672 KiB
19 Accepted 3ms 2756 KiB
20 Accepted 3ms 2980 KiB
21 Accepted 3ms 2988 KiB
22 Accepted 3ms 2968 KiB
23 Accepted 3ms 2964 KiB
24 Accepted 3ms 3096 KiB
25 Accepted 6ms 3308 KiB
26 Accepted 6ms 3412 KiB
27 Accepted 6ms 3408 KiB
28 Accepted 4ms 3488 KiB
29 Accepted 6ms 3488 KiB
30 Accepted 6ms 3620 KiB
31 Accepted 6ms 3712 KiB
32 Accepted 6ms 3740 KiB
33 Accepted 3ms 3972 KiB
subtask4 20/20
34 Accepted 3ms 3972 KiB
35 Accepted 3ms 2260 KiB
36 Accepted 3ms 2328 KiB
37 Accepted 3ms 2460 KiB
38 Accepted 3ms 2672 KiB
39 Accepted 3ms 2756 KiB
40 Accepted 3ms 2980 KiB
41 Accepted 3ms 2988 KiB
42 Accepted 3ms 2968 KiB
43 Accepted 3ms 2964 KiB
44 Accepted 3ms 3096 KiB
45 Accepted 6ms 3308 KiB
46 Accepted 6ms 3412 KiB
47 Accepted 6ms 3408 KiB
48 Accepted 4ms 3488 KiB
49 Accepted 6ms 3488 KiB
50 Accepted 6ms 3620 KiB
51 Accepted 6ms 3712 KiB
52 Accepted 6ms 3740 KiB
53 Accepted 3ms 3972 KiB
54 Accepted 565ms 4136 KiB
55 Accepted 541ms 4136 KiB
56 Accepted 559ms 4152 KiB
57 Accepted 555ms 4148 KiB
58 Accepted 575ms 4124 KiB
59 Accepted 504ms 4124 KiB
60 Accepted 411ms 4128 KiB
61 Accepted 391ms 4276 KiB
62 Accepted 486ms 4384 KiB
63 Accepted 451ms 4340 KiB
64 Accepted 432ms 4336 KiB
65 Accepted 453ms 4392 KiB
66 Accepted 432ms 4464 KiB
67 Accepted 456ms 4624 KiB
68 Accepted 465ms 4576 KiB
69 Accepted 493ms 4724 KiB
70 Accepted 477ms 4616 KiB
71 Accepted 476ms 4848 KiB
72 Accepted 481ms 4932 KiB
73 Accepted 483ms 4840 KiB
subtask5 0/40
74 Accepted 483ms 4840 KiB
75 Accepted 3ms 2260 KiB
76 Accepted 3ms 2328 KiB
77 Accepted 3ms 2460 KiB
78 Accepted 3ms 2672 KiB
79 Accepted 3ms 2756 KiB
80 Accepted 3ms 2980 KiB
81 Accepted 3ms 2988 KiB
82 Accepted 3ms 2968 KiB
83 Accepted 3ms 2964 KiB
84 Accepted 3ms 3096 KiB
85 Accepted 6ms 3308 KiB
86 Accepted 6ms 3412 KiB
87 Accepted 6ms 3408 KiB
88 Accepted 4ms 3488 KiB
89 Accepted 6ms 3488 KiB
90 Accepted 6ms 3620 KiB
91 Accepted 6ms 3712 KiB
92 Accepted 6ms 3740 KiB
93 Accepted 3ms 3972 KiB
94 Accepted 565ms 4136 KiB
95 Accepted 541ms 4136 KiB
96 Accepted 559ms 4152 KiB
97 Accepted 555ms 4148 KiB
98 Accepted 575ms 4124 KiB
99 Accepted 504ms 4124 KiB
100 Accepted 411ms 4128 KiB
101 Accepted 391ms 4276 KiB
102 Accepted 486ms 4384 KiB
103 Accepted 451ms 4340 KiB
104 Accepted 432ms 4336 KiB
105 Accepted 453ms 4392 KiB
106 Accepted 432ms 4464 KiB
107 Accepted 456ms 4624 KiB
108 Accepted 465ms 4576 KiB
109 Accepted 493ms 4724 KiB
110 Accepted 477ms 4616 KiB
111 Accepted 476ms 4848 KiB
112 Accepted 481ms 4932 KiB
113 Accepted 483ms 4840 KiB
114 Time limit exceeded 1.074s 8264 KiB
115 Time limit exceeded 1.054s 8440 KiB
116 Time limit exceeded 1.024s 8428 KiB
117 Time limit exceeded 1.049s 8476 KiB
118 Time limit exceeded 1.082s 8324 KiB
119 Time limit exceeded 1.065s 8364 KiB
120 Time limit exceeded 1.07s 8396 KiB
121 Time limit exceeded 1.065s 8348 KiB
122 Time limit exceeded 1.052s 8412 KiB
123 Time limit exceeded 1.054s 8436 KiB
124 Time limit exceeded 1.075s 8496 KiB
125 Time limit exceeded 1.057s 8480 KiB
126 Time limit exceeded 1.062s 8480 KiB
127 Time limit exceeded 1.057s 8492 KiB
128 Time limit exceeded 1.057s 8532 KiB
129 Time limit exceeded 1.082s 8412 KiB
130 Time limit exceeded 1.057s 8388 KiB
131 Time limit exceeded 1.065s 8616 KiB
132 Time limit exceeded 1.041s 8392 KiB
133 Time limit exceeded 1.049s 8424 KiB
134 Time limit exceeded 1.07s 8708 KiB
135 Time limit exceeded 1.07s 8720 KiB
136 Time limit exceeded 1.054s 8856 KiB