Cod sursa(job #1330762)

Utilizator lilian_ciobanuLilian Ciobanu lilian_ciobanu Data 30 ianuarie 2015 22:34:54
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include<fstream>
#include<algorithm>
#include<cmath>

using namespace std;

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

const long long INF=(1LL<<31);

struct Point{
    int x;
    int y;
};

bool cmpX(Point i, Point j){
    if(i.x == j.x)
        return i.y < j.y;
    else
        return i.x < j.x;
}

bool cmpY(Point i, Point j){
    if(i.y == j.y)
        return i.x < j.x;
    else
        return i.y < j.y;
}

Point Px[1000],Py[1000], Pm[1000];
int PmSize;
long double globalMinDist=INF;


long double dist(Point i, Point j){
    return sqrt(1LL*(i.x-j.x)*(i.x-j.x) + 1LL*(i.y - j.y)*(i.y - j.y));
}


long double brute(Point P[], int n){
    long double d=INF;

    for(int i=0; i< n-1; ++i)
        for(int j=i+1; j<n; ++j)
            d=min(d,dist(P[i],P[j]));

    return d;
}


void distMinMij(){

    for(int i=0; i<PmSize; ++i){
        for(int j=i+1; j<PmSize && (Pm[j].y - Pm[i].y)< globalMinDist; ++j)
            globalMinDist=min(globalMinDist , dist(Pm[i], Pm[j]));
    }

}


long double distMin(Point Px[], Point Py[], int n){

    if(n <= 3){
        return brute(Px,n);
    }

    int mid=n/2;
    Point midPoint=Px[mid];

    Point Pyl[mid+1];
    Point Pyr[n-mid];

    int lp=0, rp=0;

    for(int i=0; i<n; ++i){
        if(Py[i].x <= midPoint.x)
            Pyl[lp++] = Py[i];
        else
            Pyr[rp++] = Py[i];
    }

    globalMinDist = min(globalMinDist ,min(distMin(Px, Pyl, mid) , distMin(Px + mid, Pyr, n - mid)));


    PmSize = 0;
    for(int i = 0; i<n; ++i){
        if(abs(Py[i].x - midPoint.x) < globalMinDist){
            Pm[PmSize++] = Py[i];
        }

    }


    return globalMinDist;
}



int main(){
    int n,i,j;
    Point p;

    f>>n;

    for(i=0; i<n; ++i){
        f>>p.x>>p.y;

        Px[i]=p;
        Py[i]=p;
    }

    sort(Px, Px + n, cmpX);
    sort(Py, Py + n, cmpY);

    g<<fixed;
    g.precision(10);
    g<<distMin(Px , Py, n);


return 0;
}