AT_geocon2013_a 役人题解

cff_0102 · 2024-01-14 01:53:39 · 题解

可以将所有点按照它与原点的角度排序，并按照排序顺序，将排序后相邻的三个点组成三角形。不难证明在不考虑本题解最后的极其特殊的情况下一定能分成一百个不相交的三角形：

假设这样做后还是有两个三角形相交了，且就是下面这个三角形与另一个三角形相交（下面蓝色的是原点）。

可以看到整个三角形必然在这个范围内：

右边那条射线是原点向这三个点排序后角度最小的点射出的一条射线，左边那条是原点向这三个点中角度最大的那个点射出的一条射线。这两个射线所夹的角中一定只含一个点，也就是这三个点排序后的第二个点，不可能存在其它点。而两个三角形要相交必须要有一个三角形的顶点在这个范围内（因为左边那条线再往左、右边那条线再往右的点可以说几乎不可能被分到一个三角形中，除非出现下面的特殊情况），所以这样排序后，一定没有相交的三角形。

因此，直接按角度排序后按顺序输出编号即可。

如果本题数据不随机，应该还要避免下图特殊情况（有一个三角形的第一个点和第三个点分别在第二、四象限，这两个点的连线与坐标轴围成的三角形内包含其它点）。一种解决方法是将所有点坐标加上 1000，把所有点挪到第一象限。

#include<bits/stdc++.h>
using namespace std;
struct point{
    double angle;
    int n;
}a[300];
bool cmp(point x,point y){
    return x.angle<y.angle;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    for(int i=0;i<300;i++){
        double x,y;
        cin>>x>>y;x+=1000,y+=1000;
        a[i].angle=atan2(x,y);
        a[i].n=i+1;
    }
    sort(a,a+300,cmp);
    cout<<100<<endl;
    for(int i=0;i<300;i+=3){
        cout<<a[i].n<<" "<<a[i+1].n<<" "<<a[i+2].n<<endl;
    }
    return 0;
}

10000 分。

AT_geocon2013_a 役人 题解

AT_geocon2013_a 役人题解