Cod sursa(job #918357)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 18 martie 2013 20:23:02
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
struct pct
{int x,y;};
pct a[100002],b[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;
}

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

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);
        b[i].x=a[i].x; b[i].y=a[i].y;
    }
    sort(a+1,a+n+1,Sortar);
    sort(b+1,b+n+1,Sortare);
       // for(i=1; i<=n; i++)
//
     //  printf("%d %d\n",b[i].x,b[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
    {

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

}

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


    }
    else
    {

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

}


int main()
{
    double rez;
    Citire();
    DivImp(1,n);
    DivImpe(1,n);

    rez=sqrt(minim);
    freopen("cmap.out","w",stdout);
    printf("%f",rez);
    //Sortar();
    return 0;
}