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;
}