0585:Nearest Two Points
最近点対問題を蟻本を参考に実装。
#include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #include<cfloat> using namespace std; double EPS = 1e-10; double add(double a, double b){ if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0; return a+b; } struct point{ double x, y; }; bool cmp_x(const point& p, const point& q){ if(p.x != q.x)return p.x<q.x; return p.y < q.y; } bool comp_y(point a,point b){ return a.y<b.y; } int N; const double INF=1000000000; point A[1000000]; double closest_pair(point *a, int n){ if(n<=1)return INF; int m=n/2; double x=a[m].x; double d=min(closest_pair(a,m),closest_pair(a+m,n-m)); inplace_merge(a,a+m,a+n,comp_y); vector<point>b; for(int i=0;i<n;i++){ if(abs(a[i].x-x)>=d)continue; for(int j=0;j<b.size();j++){ double dx = a[i].x-b[b.size()-j-1].x; double dy = a[i].y-b[b.size()-j-1].y; if(dy>=d)break; d=min(d,dx*dx+dy*dy); } b.push_back(a[i]); } return d; } int main(void){ point in; cin >> N; for(int i=0;i<N;i++) cin >> A[i].x >> A[i].y; sort(A,A+N,cmp_x); cout << closest_pair(A,N) << endl; return 0; }