Cod sursa(job #1703100)

Utilizator cella.florescuCella Florescu cella.florescu Data 16 mai 2016 11:01:23
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 100000
#define INF 4611686018427387904
#define minim(a, b) (a<b?a:b)

using namespace std;

struct punct{
  int x, y;
} v[MAXN], w[MAXN], aux[MAXN];

inline long long dist(punct A, punct B){
  return 1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y);
}

int cmp(punct A, punct B){
  if(A.x==B.x)
    return A.y<B.y;
  return A.x<B.x;
}

inline int myabs(int val){
  if(val<0)
    return -val;
  return val;
}

inline void mymerge(int p1, int p2, int p3){
  int i=p1, j=p2, k=0;
  while(i<p2 && j<p3)
    if(w[i].y<w[j].y)
      aux[k++]=w[i++];
    else
      aux[k++]=w[j++];
  while(i<p2)
    aux[k++]=w[i++];
  while(j<p3)
    aux[k++]=w[j++];
  for(i=0; i<k; i++)
    w[i+p1]=aux[i];
}

long long divetimp(int st, int dr){
  long long dmin;
  int m, mij, i, j;
  if(dr-st<=0)
    return INF;
  if(dr-st<=2){
    mymerge(st, st+1, dr+1);
    dmin=dist(v[st], v[st+1]);
    if(st+2<=dr){
      dmin=minim(dmin, dist(v[st], v[st+2]));
      dmin=minim(dmin, dist(v[st+1], v[st+2]));
    }
    return dmin;
  }
  mij=(st+dr)/2;
  dmin=minim(divetimp(st, mij), divetimp(mij+1, dr));
  mymerge(st, mij+1, dr+1);
  m=0;
  for(i=st; i<=dr; i++)
    if(myabs(w[i].x-v[mij].x)<=dmin)
      aux[m++]=w[i];
  for(i=0; i<m-1; i++)
    for(j=i+1; j<m && j-i<8; j++)
      dmin=minim(dmin, dist(aux[i], aux[j]));
  return dmin;
}

int main()
{
    FILE *fin, *fout;
    int n, i;
    fin=fopen("cmap.in", "r");
    fscanf(fin, "%dn", &n);
    for(i=0; i<n; i++)
      fscanf(fin, "%d%d", &v[i].x, &v[i].y);
    fclose(fin);
    sort(v, v+n, cmp);
    for(i=0; i<n; i++)
      w[i]=v[i];
    fout=fopen("cmap.out", "w");
    fprintf(fout, "%lf\n", sqrt(divetimp(0, n-1)));
    fclose(fout);
    return 0;
}