AI Summary
将点投影到x轴，按坐标排序后匹配同色点对，利用容斥保证不交，得到轨道连线。
P14511 [NFLSPC #8] 轨道交通
这道题第一眼并没有思路…
然后我们考虑特殊性质，发现特殊性质描述了所有点都在对角线上的情况。
我们考虑特殊做法，根据容斥原理，我们可以得到：若按照顺序遍历，找到一对颜色相同的点，连边，并在遍历队列中删除所有刚刚遍历过的点，因为每次最多删除 个点，每个颜色删除 个，最多删除 次，但是每个颜色都有 个点，那么保证有完全不重合交点。
我们从特殊性质出发得出做法：将所有点投影到 x 轴上，有一个显而易见的结论：
投影之后不相交的线段投影前也不相交。
那么投影完之后按照特殊做法相同方式处理即可。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2005;
int n;
struct point {
int x,col,id;
bool operator < (const point p) const {
return x<p.x;
}
};
vector <point> p;
int tmp[N];
pair <int,int> res[N];
signed main() {
Cios;
int T;
cin>>T;
while (T--) {
cin>>n;
p.clear();
for (int i=1;i<=n;i++) {
for (int j=1;j<=n+1;j++) {
int x,y;
cin>>x>>y;
p.push_back({x,i,j});
}
}
sort(p.begin(),p.end());
for (auto [x,col,id]:p) {
if (!tmp[col]) tmp[col]=id;
else if (res[col].first==0&&res[col].second==0){
res[col]={tmp[col],id};
for (int i=1;i<=n;i++) tmp[i]=0;
}
}
for (int i=1;i<=n;i++) cout<<res[i].first<<" "<<res[i].second<<"\n";
for (int i=1;i<=n;i++) tmp[i]=0,res[i]={0,0};
}
return 0;
}
评论（0）
暂无评论