Cod sursa(job #1614056)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 25 februarie 2016 19:42:45
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

struct Punct
{   int x, y;
} a[100001];

int sol, n;

ifstream f("cmap.in");
ofstream g("cmap.out");

inline bool cmp(const Punct &a, const Punct &b)
{   if (a.x==b.x)
        return a.y<b.y;
    return a.x+a.y<b.x+b.y; // Sortam sirul dupa suma coordonatelor
}

int main()
{   int i, j;
    f>>n;
    for (i=1; i<=n; ++i)
        f>>a[i].x>>a[i].y;
    sort(a+1, a+n+1, cmp);
    unsigned long long dist, mini=1LL<<60; //initializam mini cu 2^60
    Punct A, B;
    for (i=1; i<n; ++i)
        for (j=i+1; j<=i+7 && j<=n; ++j) // Verificam fiecare punct P doar cu urmatoarele 7 in sirul sortat
        {   A=a[i];
            B=a[j];
            dist=1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y);
            if (dist<mini)
            {   mini=dist;
                //sol=i;
            }
        }
    //g<<a[sol].x<<' '<<a[sol].y;
    g<<setprecision(6)<<fixed<<sqrt(double(mini));
    return 0;
}