Cod sursa(job #1305965)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 30 decembrie 2014 13:14:10
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#include <algorithm>
#include <cmath>
FILE *fin,*fout;
double mini(double a,double b)
{
    if(a<b) return a;
    return b;
}
int n;
struct str
{
    int x;
    int y;
}a[100001];
int comp(str a,str b)
{
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
double gasut(int p1,int p2)
{
    double minim=100000000.00000000;
    int size=p2-p1+1;
    if(size<=4)
    {
        for(int i=p1;i<=p2;i++)
        {
            for(int j=i+1;j<=p2;j++)
            {
                if(minim>sqrt((double)pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2))) minim=sqrt((double)pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2));
            }
        }
        return minim;
    }
    int mij=(p1+p2)/2;
    return mini(gasut(p1,mij-1),gasut(mij,p2));
}
double gas(int p1,int p2)
{
    double minim=100000000.00000000;
    int size=p2-p1+1;
    if(size<=3)
    {
        for(int i=p1;i<=p2;i++)
        {
            for(int j=i+1;j<=p2;j++)
            {
                if(minim>sqrt((double)pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2))) minim=sqrt((double)pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2));
            }
        }
        return minim;
    }
    int mij=(p1+p2)/2;
    return mini(gasut(p1,mij-1),gasut(mij+1,p2));
}
int main()
{
    fin=fopen("cmap.in","r");
    fout=fopen("cmap.out","w");
    fscanf(fin,"%d",&n);
    for(int i=1;i<=n;i++)
    {
        fscanf(fin,"%d%d",&a[i].x,&a[i].y);
    }
    std::sort(a+1,a+n+1,comp);
    double lung,mi=gas(1,n);
    int j=(n+1)/2;
    for(int i=j-1;i>=1;i--)
    {
        lung=sqrt((double)pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2));
        if(lung<mi) mi=lung;
        else break;
    }
    for(int i=j+1;i<=n;i++)
    {
        lung=sqrt((double)pow((a[i].x-a[j].x),2)+pow((a[i].y-a[j].y),2));
        if(lung<mi) mi=lung;
        else break;
    }
    fprintf(fout,"%.6f",mi);
}