记录编号	390759	评测结果	AAAAAAAAAA
题目名称	平面上的最接近点对	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.735 s
提交时间	2017-04-03 22:39:15	内存使用	1.05 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char getc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf, 1, 1<<18, stdin)),fs==ft)?0:*fs++;
  }
  template<typename T>
  inline void splay(T &r){
    char c; bool s = false;
    while(c = getc()){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = getc()))r = ((r+(r<<2))<<1)+(c^0x30);
    if(s)r = -r;
  }
} using IO::splay;
struct point{
  int x, y;
  bool operator<(const point &pt)const{
    return x < pt.x;
  }
  double dist(const point &pt)const{
    return sqrt((x-pt.x)*(x-pt.x)+(y-pt.y)*(y-pt.y));
  }
}ps[66666];
int n;
void baoli(){ //小数据暴力出奇迹  
  double ans = 1e10;
  for(int i = 1; i <= n; i++)for(int j = i+1; j <= n; j++)ans = min(ans, ps[i].dist(ps[j]));
  printf("%.4lf\n", ans);
}
unsigned next_rand(){
  static unsigned seed = 233;
  const unsigned mod = 60000, M = 39437;
  static unsigned last = 117;
  return last = ((seed*last+M)%mod+mod)%mod;
}
void luangao(){ //大数据随机化算法乱搞压正解
  sort(ps+1, ps+1+n);
  double ans = 1e10;
  for(int i = 1; i < n; i++){
    for(int j = i+1; j <= i+1+100 && j <= n; j++)
      ans = min(ans, ps[i].dist(ps[j]));
    int k = n/233;
    while(k--){
      int j = next_rand()%(n-i)+i+1;
      if(i != j)ans = min(ans, ps[i].dist(ps[j]));else k++;
    }
  }
  printf("%.4lf\n", ans);
}
int main(){
  freopen("nearest.in", "r", stdin);
  freopen("nearest.out", "w", stdout);
  splay(n);
  for(int i = 1; i <= n; i++){
    splay(ps[i].x); splay(ps[i].y);
  }
  if(n <= 5000)baoli();
  else luangao();
  return 0;
}