Cod sursa(job #1275359)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 25 noiembrie 2014 01:10:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define inf 20000000
using namespace std;
struct pct{
    long long x;
    long long y;
}x[100100],y[100100],z[100100];
long long n,i,j,a,b;
FILE *f,*g;
int cmp(pct a,pct b){
    return a.x<b.x;
}
long long lg(pct a,pct b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long minim(long long a,long long b){
    if(a<b)
        return a;
    return b;
}
long long mod(long long a){
    if(a<0)
        return -a;
    return a;
}
void intercl (int st, int mid, int dr) {
    int i=st,j=mid+1,nr=0;
    while (i<=mid&&j<=dr)
        if (x[i].x<=x[j].x)
            y[++nr]=x[i++];
        else
            y[++nr]=x[j++];
    for (;i<=mid;i++)
        y[++nr]=x[i];
    for (;j<=dr;j++)
        y[++nr]=x[j];
    for (i=st;i<=dr;i++)
        x[i]=y[i-st+1];
}
long long sol(int st, int dr) {
    long long mid,r;
    int k;
    if (st==dr)
        return inf;
    if(dr-st==1){
        intercl(st,st,dr);
        return lg(x[st],x[dr]);
    }
    mid=(st+dr)/2;
    r=minim(sol(st,mid),sol(mid+1,dr));
    intercl(st,mid,dr);
    k=0;
    for (int i=st;i<=dr;i++)
        if (x[mid].x-x[i].x<=r&&x[i].x-x[mid].x<=r)
            y[++k]=x[i];
    for (int i=1;i<=k;i++)
        for (int j=1;j<=7&&j+i<=k;j++)
            r=minim(r,lg(y[i],y[i+j]));

    return r;
}
int main(){
    f=fopen("cmap.in","r");
    g=fopen("cmap.out","w");
    fscanf(f,"%lld",&n);
    for(i=1;i<=n;i++){
        fscanf(f,"%lld%lld",&x[i].x,&x[i].y);
    }
    sort(x+1,x+n+1,cmp);
    fprintf(g,"%.6lf",(double)sqrt(sol(1,n)));



    fclose(f);
    fclose(g);
    return 0;
}