#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <queue>
#include <stack>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;
int n;
struct DSU
{
int par[MAXN];
int dep[MAXN];
void build()
{
std::iota(par + 1, par + 1 + 2 * n, 1);
std::fill(dep + 1, dep + 1 + 2 * n, 1);
}
int find(int node)
{
if (par[node] == node) return node;
return par[node] = find(par[node]);
}
void connect(int u, int v)
{
u = find(u);
v = find(v);
assert(u != v);
if (dep[u] > dep[v])
{
std::swap(u, v);
}
if (dep[u] == dep[v])
{
dep[v]++;
}
par[u] = v;
}
bool areConnected(int u, int v)
{
return find(u) == find(v);
}
};
DSU dsu;
struct Point
{
llong x, y;
};
llong dist(Point a, Point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
Point p[MAXN];
int idx[MAXN];
struct MstElement
{
int x, y;
friend bool operator < (const MstElement &a, const MstElement &b)
{
return dist(p[a.x], p[a.y]) > dist(p[b.x], p[b.y]);
}
};
std::priority_queue <MstElement> mst;
void pushMIN(int x, int y)
{
llong distA = dist(p[x], p[y]);
llong distB = dist(p[x], p[n + y]);
llong distC = dist(p[n + x], p[y]);
llong distD = dist(p[n + x], p[n + y]);
if (distA <= distB && distA <= distC && distA <= distD)
{
mst.push({x, y});
return;
}
if (distB <= distC && distB <= distD)
{
mst.push({x, n + y});
return;
}
if (distC <= distD)
{
mst.push({n + x, y});
return;
}
mst.push({x + n, y + n});
}
std::mt19937 rng(69420);
void solve()
{
dsu.build();
for (int i = 1 ; i <= n ; ++i)
{
dsu.connect(i, n + i);
}
std::vector <std::pair <Point,Point>> answer;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= n ; ++j)
{
if (i == j) continue;
if (idx[i] == 0 || dist(p[i], p[j]) < dist(p[i], p[idx[i]]))
{
idx[i] = j;
}
}
pushMIN(i, idx[i]);
}
while (answer.size() < n - 1)
{
auto [x, y] = mst.top();
mst.pop();
if (dsu.areConnected(x, y))
{
continue;
}
answer.push_back({p[x], p[y]});
dsu.connect(x, y);
if (x > n) x -= n;
if (y > n) y -= n;
idx[x] = idx[y] = 0;
for (int i = 1 ; i <= n ; ++i)
{
if (dsu.areConnected(x, i)) continue;
if (idx[x] == 0 || dist(p[x], p[i]) < dist(p[x], p[idx[x]]))
{
idx[x] = i;
}
}
for (int i = 1 ; i <= n ; ++i)
{
if (dsu.areConnected(y, i)) continue;
if (idx[y] == 0 || dist(p[y], p[i]) < dist(p[y], p[idx[y]]))
{
idx[y] = i;
}
}
pushMIN(x, idx[x]);
pushMIN(y, idx[y]);
}
// assert(answer.size() == n - 1);
for (const auto &[p1, p2] : answer)
{
std::cout << p1.x << ' ' << p1.y << ' ' << p2.x << ' ' << p2.y << '\n';
}
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> p[i].x >> p[i].y >> p[n + i].x >> p[n + i].y;
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
roads.cpp: In function 'void solve()':
roads.cpp:134:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<Point, Point> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
134 | while (answer.size() < n - 1)
| ~~~~~~~~~~~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Execution timed out |
1090 ms |
5228 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
10 ms |
4444 KB |
Output is correct |
4 |
Failed |
840 ms |
5960 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
10 ms |
4444 KB |
Output is correct |
4 |
Failed |
835 ms |
5860 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
10 ms |
4440 KB |
Output is correct |
4 |
Failed |
825 ms |
5424 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
10 ms |
4860 KB |
Output is correct |
5 |
Failed |
847 ms |
5936 KB |
Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])" |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Execution timed out |
1082 ms |
5240 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |