Problem G. Invited Speakers
Statement
给定 $2n$ 个不同的点 $(x_i,y_i)$，$A$ 类型和 $B$ 类型各 $n$ 个，保证不存在三点共线。希望你能给出一种方案把它们配对成 $n$ 对 $AB$，并且每对 $AB$ 之间用折线（$[1, 100]$ 条首尾相连的线段）相连，折线之间两两不交。有 $z$ 组测试数据。
$1 \leq z \leq 200$
$1 \leq n \leq 6$
$0 \leq |x_i|,|y_i| \leq 100$
Solution
我读的题，第一反应是：就这？
还害我确认了好几遍题意和数据范围。
精通脚撕 FFT 的各种姿势的队友 Luowaterbi 曾经告诉我，没有三点共线的时候，两种一样多的点必然存在一种配对方案使得每对之间只用一条线段相连并且所有线段都不交。既然这题数据范围这么小，直接大力枚举配对方案，再大力枚举判断是否存在两线段交就行了。时间复杂度 $O(n!n^2)$。
由于我计算几何过于垃圾不想写，我就交给 triple_a 写了。triple_a 写得也很有意思，没用到计算几何的线段交判定，直接 $O(n!n)$ 取所有线段长度之和最小的方案，而这其实就是所有线段都不交的那个方案。
官方题解是个构造，懒得看具体折线怎么画了，反正意义不大，出题人可能是没想到有结论。
Code (By triple_a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
int t,n;
int p[7],res[7];
pair<int,int> a[7],b[7];
double dist;
int main(){
cin>>t;
while (t--){
cin>>n;
for (int i=0;i<n;++i){
cin>>a[i].first>>a[i].second;
}
for (int i=0;i<n;++i){
cin>>b[i].first>>b[i].second;
}
dist=1e9;
for (int i=0;i<n;++i){
p[i]=i;
}
auto f=[&](pair<int,int>u, pair<int,int> v){
return (u.first-v.first)*(u.first-v.first)+(u.second-v.second)*(u.second-v.second);
};
do{
double sum=0;
for (int i=0;i<n;++i){
sum+=sqrt(f(a[i],b[p[i]]));
}
if (sum<dist){
dist=sum;
for (int i=0;i<n;++i){
res[i]=p[i];
}
}
}while(next_permutation(p,p+n));
for (int i=0;i<n;++i){
cout<<2<<" "<<a[i].first<<" "<<a[i].second<<" "<<b[res[i]].first<<" "<<b[res[i]].second<<endl;
}
}
}
|