#include <bits/stdc++.h>
using namespace std;
struct ponto
{
long long x, y;
ponto(long long X = 0, long long Y = 0) : x(X), y(Y) {}
ponto operator+ (ponto outro) const {return ponto(x + outro.x, y + outro.x);}
ponto operator- (ponto outro) const {return ponto(x - outro.x, y - outro.y);}
long long operator* (ponto outro) const {return (x * outro.x) + (y*outro.y);}
long long operator^ (ponto outro) const {return (x * outro.y) - (y*outro.x);}
bool operator< (ponto outro) const {return (x == outro.x ? y < outro.y : x < outro.x);}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(69);
vector<int> pai, sub;
int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int x, int y, vector<pair<int, int>> &resp)
{
int px = find(x), py = find(y);
if (px == py) return;
if (sub[px] < sub[py]) swap(px, py);
resp.emplace_back(x, y);
pai[py] = px; sub[px] += sub[py];
}
void dc(vector<pair<int, int>> &activeE, vector<int> &activeP, vector<pair<int, int>> &resp, const vector<ponto> &v)
{
if (activeE.empty())
{
sort(activeP.begin(), activeP.end(), [&](const int &a, const int &b) {return v[a] < v[b];});
for (int i = 0; i < activeP.size()-1; i++) une(activeP[i], activeP[i+1], resp);
return;
}
int idE = uniform_int_distribution<int>(0, (int)activeE.size()-1)(rng);
auto [l, r] = activeE[idE];
if (v[r] < v[l]) swap(l, r);
vector<pair<int, int>> lE, rE;
vector<int> lP(1, l), rP(1, r);
for (auto p : activeP)
{
long long dir = ((v[r]-v[l])^(v[p]-v[l]));
if (dir == 0) dir = ((v[p] < v[l]) ? -1 : 1);
if (dir < 0LL) lP.push_back(p);
else rP.push_back(p);
}
for (auto [L, R] : activeE)
{
if (L == l && R == r) continue;
long long dirL = ((v[r]-v[l])^(v[L]-v[l]));
if (dirL == 0) dirL = ((v[L] < v[l]) ? -1 : 1);
long long dirR = ((v[r]-v[l])^(v[R]-v[l]));
if (dirR == 0) dirR = ((v[R] < v[l]) ? -1 : 1);
if (dirL * dirR > 0LL) //Dois p/ mesmo lado, nenhum alinhado
{
if (dirL < 0LL) lE.emplace_back(L, R);
else rE.emplace_back(L, R);
}
else
{
if (dirL < 0LL) lP.push_back(L), rP.push_back(R);
else lP.push_back(R), rP.push_back(L);
}
}
dc(lE, lP, resp, v);
dc(rE, rP, resp, v);
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<ponto> v(2*N);
pai.resize(2*N); iota(pai.begin(), pai.end(), 0);
sub.resize(2*N); fill(sub.begin(), sub.end(), 1);
for (int i = 0; i < 2*N; i++) cin >> v[i].x >> v[i].y;
vector<pair<int, int>> resp;
vector<pair<int, int>> activeE; vector<int> activeP;
for (int i = 0; i < 2*N; i+=2) une(i, i+1, activeE);
dc(activeE, activeP, resp, v);
for (auto &[i, j] : resp) cout << v[i].x << " " << v[i].y << " " << v[j].x << " " << v[j].y << '\n';
}
Compilation message
roads.cpp: In function 'void dc(std::vector<std::pair<int, int> >&, std::vector<int>&, std::vector<std::pair<int, int> >&, const std::vector<ponto>&)':
roads.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 0; i < activeP.size()-1; i++) une(activeP[i], activeP[i+1], resp);
| ~~^~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Failed |
0 ms |
348 KB |
Condition failed: "!Cross(S[*pi], S[*pa])" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
551 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
543 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
555 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Failed |
0 ms |
348 KB |
Condition failed: "!Cross(S[*pi], S[*pa])" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
528 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
