Cod sursa(job #1587135)

Utilizator gapdanPopescu George gapdan Data 1 februarie 2016 20:16:22
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 1000005

using namespace std;

int n,i;
double doy,dox;
struct punct
{
    int x,y;
}v[NMAX],aux[NMAX];

bool cmp(punct p, punct r)
{
    return(p.y>r.y);
}

double calc(punct a,punct b)
{
    return (double)sqrt((double)(a.x-b.x)*(a.x-b.x) + (double)(a.y-b.y)*(a.y-b.y));
}

double dist(int st,int dr,punct &X,punct &Y)
{
    if(st == dr) return 1e10;
    int mij=(st+dr)/2;
    int i,j,l,r,k;
    double rez1,rez2;
    punct A,B,C,D;
    rez1=dist(st,mij,A,B);
    rez2=dist(mij+1,dr,C,D);
    if(rez1<0.01 || rez2 < 0.01) return 0.01;
    if(rez1>rez2)
    {
        rez1=rez2;
        X=C;
        Y=D;
    }
    else X=A,Y=B;
    l=st;r=mij+1;k=0;
    while(l <= mij || r <= dr)
    {
        if(r>dr || (l<=mij && v[l].y < v[r].y))
        {
            aux[++k]=v[l];
            ++l;
        }
        else
        {
            aux[++k]=v[r];
            ++r;
        }
    }

    k=0;
    for(i=st;i<=dr;++i) v[i]=aux[++k];

    for(i=st;i<=dr;++i)
        for(j=i+1; j<=dr && v[j].y - v[i].y <= rez1; ++j)
        {
            rez2=calc(v[i],v[j]);
            if(rez2 < rez1)
            {
                rez1=rez2;
                X=v[i];
                Y=v[j];
            }
        }
    return rez1;
}

int main()
{
    freopen("harta2.in","r",stdin);
    freopen("harta2.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        {
            scanf("%d%d",&v[i].x,&v[i].y);
            v[i].y=v[i].y*3;
        }
    sort(v+1,v+n+1,cmp);
    punct X,Y;
    double d=dist(1,n,X,Y);
    dox=abs(X.x-Y.x);
    doy=abs(X.y-Y.y);
    if(X.x > Y.x)
    {
        d=max(dox,doy);
    }
    else
    {
        d=min(dox,doy);
    }
    printf("%0.4f",d/3.0);
    return 0;
}