Cod sursa(job #1275355)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 25 noiembrie 2014 00:46:15
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct pct{
    int x;
    int y;
}x[100100],y[100100],z[100100];
int n,i,j,a,b;
FILE *f,*g;
int cmp(pct a,pct b){
    return a.x<b.x;
}
void intercl(int st,int mid,int dr){
    int i=st;
    int j=mid+1;
    int nr=st-1;
    while(i<=mid&&j<=dr){
        if(x[i].y<x[j].y){
            y[++nr].x=x[i].x;
            y[nr].y=x[i].y;
            i++;
        }
        else{
            y[++nr].x=x[j].x;
            y[nr].y=x[j].y;
            j++;
        }
    }
    for(;i<=mid;i++){
        y[++nr].x=x[i].x;
        y[nr].y=x[i].y;
    }
    for(;j<=dr;j++){
        y[++nr].x=x[j].x;
        y[nr].y=x[j].y;
    }
    for(i=st;i<=dr;i++){
        x[i].x=y[i].x;
        x[i].y=y[i].y;
    }
}
int lg(pct a,pct b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int minim(int a,int b){
    if(a<b)
        return a;
    return b;
}
int mod(int a){
    if(a<0)
        return -a;
    return a;
}
int sol(int st,int dr){
    int a,as,ad,mid,vmin,nrr;
    if(dr-st==1){
        a=lg(x[st],x[dr]);
        intercl(st,st,dr);
        return a;
    }
    if(dr-st==2){
        a=minim( lg(x[st],x[st+1]), minim( lg(x[st],x[st+2]) , lg(x[st+1],x[st+2]) ) );
        intercl(st,st,st+1);
        intercl(st,st+1,dr);
        return a;
    }
    mid=(dr+st)/2;
    as=sol(st,mid);
    ad=sol(mid+1,dr);
    intercl(st,mid,dr);
    vmin=minim(as,ad);
    nrr=0;
    for(i=st;i<=dr;i++){
        if(mod(x[mid].x-x[i].x)<vmin){
            z[++nrr].x=x[i].x;
            z[nrr].y=x[i].y;
        }
    }
    for(i=1;i<nrr;i++){
        for(j=i+1;j<=nrr,j<=i+7;j++){
            vmin=minim(vmin, lg(x[i],x[j]) );
        }
    }
    return vmin;
}
int main(){
    f=fopen("cmap.in","r");
    g=fopen("cmap.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(f,"%d%d",&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;
}