四边形不等式优化
我一开始直接写了一个旋转卡壳然后WA了
搜了一下题解，发现这样不对(有可能点会靠后一些)
需要优化
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=500005;
int n,T,ans[N];
struct Point{
long long x,y,id;
Point(){}
Point(long long sa,long long sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y+B.y);}
friend Point operator*(Point A,long long B){return Point(A.x*B,A.y*B);}
friend long long operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
}poi[2*N];
long long Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
bool cmp(int i,int j,int k){
long long x=Dist(poi[i],poi[j]),y=Dist(poi[i],poi[k]);
if(j<i || j>i+n)x=-x;
if(k<i || k>i+n)y=-y;
return x==y?poi[j].id>poi[k].id:x<y;
}
void Find(int l,int r,int L,int R){
if(l>r)return;
int mid=l+r>>1,M=L;
for(int i=L+1;i<=R;i++)if(cmp(mid,M,i))M=i;
ans[mid]=poi[M].id;
Find(l,mid-1,L,M);Find(mid+1,r,M,R);
}
int main(){
freopen("2739.in","r",stdin);
freopen("2739.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld %lld",&poi[i].x,&poi[i].y),poi[i].id=i;
if(n==1){puts("1");continue;}
if(n==2){puts("2\n1");continue;}
for(int i=n+1;i<=2*n;i++)poi[i]=poi[i-n];
Find(1,n,1,n<<1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
}
return 0;
}
评论 (0)
