求助!
查看原帖
求助!
416511
三重门123456楼主2021/6/6 17:59

求大佬指正!

#include <iostream>
#include <bits/stdc++.h>
//#include <cmath>
//#include <algorithm>
//#include <cstdio>
using namespace std;
struct point{
	double x,y;
	/*bool operator < (const point& other){
		return (x!=other.x ? x>other.x : y>other.y );
	};*/
}p[200010];
int temp[2000020];

bool cmps(const int &a,const int &b)
{
    return p[a].y<p[b].y;
}

bool cmp(const point a,const point other){
	return (a.x!=other.x ? a.x>other.x : a.y>other.y );
}
double dis(int i,int j){
	return sqrt( (p[i].x-p[j].x)*(p[i].y-p[j].y)*(p[i].x-p[j].x)*(p[i].y-p[j].y) );
}
double dc(int left,int right){
	double ans=2<<18,r1,r2;
	if(left==right)return ans;
	if(left+1==right)return dis(left,right);
	int mid=(left+right)/2;
	r1=dc(left,mid);
	r2=dc(mid+1,right);
	ans=min(r1,r2);
	
	int k=0;
	for(int i=left;i<=right;i++)
        if(fabs(p[i].x-p[mid].x)<=ans)
            temp[k++]=i;
    sort(temp,temp+k,cmps);
    for(int i=0;i<k;i++)
        for(int j=i+1;j<k&&p[temp[j]].y-p[temp[i]].y<ans;j++)
            ans=min(ans,dis(temp[i],temp[j]));
    return ans; 
	/*
	for(int i=0;i<right;i++){
		if(i==mid)continue;
		ans=min(dis(i,mid),ans);
	}
	return ans;
	*/
}
int main( )
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i].x>>p[i].y;
	}
	sort(p,p+n,cmp);
	double ans=dc(0,n-1);
	printf("%.4lf",ans);
	return 0;
}
2021/6/6 17:59
加载中...