Cod sursa(job #2025359)

Utilizator EricEric Vilcu Eric Data 22 septembrie 2017 17:10:50
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int i,j,n,l[1000001],k;
double S;
struct pn{int i,j;} a[100001];
bool ss(pn A,pn B)
{
    if(A.i>B.i)return 0;
    if(A.i==B.i&&A.j>B.j)return 0;
    return 1;
}
void di(int b,int e)
{
    if(e-b<4)
    {
        double s=0;
        int t1,t2;
        for(i=b;i<e;++i)for(j=i+1;j<=e;++j)
        {
            t1=a[i].i-a[j].i;t2=a[i].j-a[j].j;
            s=(float)sqrt(t1*t1+t2*t2);
            if (s<S)S=s;
        }
    }
    else
    {
        int m=(e+b)/2;int cm=a[m].i+1;
        di(b,m);di(m+1,e);
        int b1=m,e1=m,s=2*S;
        while(a[b1].i>=cm-s)b1--;
        while(a[e1].i<=cm+s)e1--;
        int t1,t2;
        for(i=b1;i<=m;++i)for(j=m+1;j<=e1;++j)
        {
            t1=a[i].i-a[j].i;t2=a[i].j-a[j].j;
            s=(float)sqrt(t1*t1+t2*t2);
            if (s<S)S=s;
        }
    }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)f>>a[i].i>>a[i].j;
    sort(a+1,a+n+1,ss);
    S=(float)sqrt((a[1].i-a[2].i)*(a[1].i-a[2].i)+(a[1].j-a[2].j)*(a[1].j-a[2].j));
    di(1,n);
    i=S;
    g<<i<<'.';
    i=(S-i)*1000000;
    g<<i/100000<<(i/10000)%10<<(i/1000)%10<<(i/100)%10<<(i/10)%10<<i%10;
}