为什么我的代码会出现超时和运行时错误
查看原帖
为什么我的代码会出现超时和运行时错误
1496514
BUZYKXZZY楼主2024/10/5 16:28
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
int n;
const int maxn=100001;
struct point{
	double x;
	double y;
}arr1[maxn];
vector<point> arr2;
bool cmp1(point a,point b){
	return a.x>b.x;
}
bool cmp2(point a,point b){
	return a.y>b.y;
}
double dis(point a,point b){
	double x=(a.x-b.x)*(a.x-b.x);
	double y=(a.y-b.y)*(a.y-b.y);
	double d=sqrt(x+y);
}
double solve(int left,int right){
	if(left==right){
		return 2e9;
	}
	if(left+1==right){
		return dis(arr1[left],arr1[right]);
	}
	int mid=(left+right)/2;
    double d1=solve(left,mid);
	double d2=solve((mid+1),right);
	double d=min(d1,d2);
    //cout<<"d1="<<d1<<endl;
    for(int i=0;i<n;i++){
    	if(fabs(arr1[i].x-arr1[mid].x)<d){
    		arr2.push_back(arr1[i]);
		}
	}
	int index=arr2.size();
	sort(arr2.begin(),arr2.end(),cmp2);
	for(int i=0;i<index;i++){//计算中间最短距离
		for(int j=i+1;j<index&&arr2[j].y-arr2[i].y<d;j++){
			    double d3=dis(arr2[i],arr2[j]);
			    if(d>d3){
			    	d=d3;
				}
			}
		}
		return d;
	}
int main() {
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr1[i].x>>arr1[i].y;
	}
	sort(arr1,arr1+n,cmp1);
	double r=solve(0,n-1);
	printf("%.4f",r);
    return 0;
}
2024/10/5 16:28
加载中...