Cod sursa(job #914230)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 13 martie 2013 23:06:29
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct pct
{int x,y;};
pct a[100002];
int n;
long long minim=123456789101213;
int ax,ay,bx,by;


bool Sortar(pct c, pct d)
{
    if(c.x==d.x) return c.y<d.y;
    return c.x<d.x;
}

void Citire()
{
    int i;
    freopen("cmap.in","r",stdin);
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d %d",&a[i].x,&a[i].y);
    }
    sort(a+1,a+n+1,Sortar);
//        for(i=1; i<=n; i++)
//
//       printf("%d %d\n",a[i].x,a[i].y);

}

void DivImp(int p1, int p2)
{
    int i,j;
    long long x;
    if(p2-p1<=3)
    {
        for(j=p1; j<p2; j++)
        for(i=j+1; i<=p2; i++)
        {
            x=(a[j].x-a[i].x)*(a[j].x-a[i].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
            if(x<minim) {minim=x; ax=a[i].x; ay=a[i].y; bx=a[j].x; by=a[j].y;}
        }
        //printf("%d %d\n",p1,p2);

    }
    else
    {
        x=(a[p2].x-a[p2-1].x)*(a[p2].x-a[p2-1].x)+(a[p2-1].y-a[p2].y)*(a[p2-1].y-a[p2].y);
        if(x<minim) {minim=x; ax=a[p1].x; ay=a[p1].y; bx=a[p2].x; by=a[p2].y;  }

        x=p2/2;
        //printf("%d %d=\n",p1,p2);
        DivImp(p1,(p1+p2)/2);
        DivImp((p1+p2)/2-1,p2);
    }

}


int main()
{
    double rez;
    Citire();
    DivImp(1,n);
    rez=sqrt(minim);
    freopen("cmap.out","w",stdout);
    printf("%f",rez);
    //Sortar();
    return 0;
}