题解 CF1254C 【Point Ordering】

2020-05-14 17:10:39


前置知识:向量与叉积。

考虑对三角形面积的询问有什么用。

然后发现,对于一条固定的线段,由于没有点之间的确切的距离,以这条线段为一边的三角形的面积可以转化为另一个顶点到这条线段所在直线的距离(即这个三角形的高)。

于是,对于询问 $1\ i\ j\ k$ ,当 $i,\ j$ 固定时,这个询问转化为询问点 $k$ 到直线 $A_iA_j$ 的距离。

对于由 $2$ 个在凸包上相邻的点连接组成的直线,其他点按逆时针排序后到这条直线的距离显然是先变大再变小,于是只要找到那个离这条直线最远的点,通过询问 $\vec{A_iA_j}\times\vec{A_iA_k}$ 的正负判断在其他点在这个点的哪一边,然后两边分别按到直线的距离排序即可得到答案,要注意排序的方式。

以上操作需要进行 $2n-4$ 次询问,还剩 $n+4$ 次询问,只需要在 $n+4$ 次询问内找到任意 $2$ 个在凸包上相邻的点即可。

可以钦定其中一个点是 $A_1$ ,然后通过询问 $\vec{A_1A_j}\times\vec{A_1A_k}$ 的正负就能很容易地求出一个与 $A_1$ 相邻的点,这一步需要询问 $n-2$ 次。

于是通过 $3n-6$ 次询问就能求出答案。

代码实现难度不高,我自认为自己代码可读性挺高的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1005
int n;
struct node{
    int s,a,pos;
}t[N];
bool cmp(node x,node y){
    if(x.a<y.a)return 1;
    if(x.a>y.a)return 0;
    if(x.a==1)return x.s>y.s;
    return x.s<y.s;
}
signed main(){
    scanf("%lld",&n);
    int maxn=-1,x=2,y;
    for(int i=1;i<=n;i++)
        t[i].pos=i;
    for(int i=3;i<=n;i++){
        printf("2 1 %lld %lld\n",x,i);
        fflush(stdout);
        scanf("%lld",&y);
        if(y==1)x=i;
    }
    for(int i=2;i<=n;i++){
        if(i==x)continue;
        printf("1 1 %lld %lld\n",x,i);
        fflush(stdout);
        scanf("%lld",&t[i].s);
        if(t[i].s>maxn)maxn=t[i].s,y=i;
    }
    x=y;
    for(int i=2;i<=n;i++){
        if(i==x)continue;
        printf("2 1 %lld %lld\n",x,i);
        fflush(stdout);
        scanf("%lld",&t[i].a);
    }
    sort(t+1,t+n+1,cmp);
    printf("0 1 ");
    for(int i=1;i<=n;i++)
        if(t[i].pos!=1)printf("%lld ",t[i].pos);
    return 0;
}