148pts求助

P7883 平面最近点对(加强加强版)

Siegerkranz_2735 @ 2023-10-04 15:47:48

按照第一篇题解思路写了一个,结果148有两个点wa了

#include<bits/stdc++.h>
#define dis(i,j) (point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)
using namespace std;
struct idx{
    long long x,y;
    double tx,ty,txy;
}point[400005];
int n;
long long ans=9223372036854775807;
bool cmp(idx a,idx b){return a.txy<b.txy;}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>point[i].x>>point[i].y;
        point[i].tx=cos(1.14)*point[i].x+sin(1.14)*point[i].y;
        point[i].ty=cos(1.14)*point[i].y-sin(1.14)*point[i].x;
        point[i].txy=point[i].tx*point[i].ty;
    }
    sort(point+1,point+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=min(n,i+50);j++){
            ans=min(ans,dis(i,j));
        }
    }
    printf("%lld",ans);
    return 0;
}

by Hughpig @ 2023-10-04 15:57:26

@2735 随机旋转角度 issue

把参数改成2.34


by Siegerkranz_2735 @ 2023-10-04 15:58:08

@Hughpig 谢谢


|