Cod sursa(job #1587562)

Utilizator somuBanil Ardej somu Data 2 februarie 2016 11:46:15
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <climits>
#include <cmath>

#define nmax 100001

using namespace std;

ifstream fi("cmap.in");
ofstream fo("cmap.out");

double minDist;
int n;

struct point {
    long long x, y;
} P[nmax];

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

bool cmpX(point a, point b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

bool cmpY(point a, point b)
{
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

void cmap(int st, int dr)
{

    if (dr <= st)
        return;

    if (dr - st == 1)
    {
        minDist = min(minDist, calcDist(P[st], P[dr]));
        return;
    }

    int mid = (st + dr) >> 1;

    cmap(st, mid);
    cmap(mid+1, dr);

}

int main()
{

    fi >> n;
    for (int i = 1; i <= n; i++)
        fi >> P[i].x >> P[i].y;

    minDist = LONG_LONG_MAX;

    sort(P+1, P+n+1, cmpX);

    cmap(1, n);

    int mid = (n + 1) >> 1;

    minDist = min(minDist, calcDist(P[(mid)], P[mid + 1]));

    sort(P+1, P+n+1, cmpY);

    cmap(1, n);

    mid = (n + 1) >> 1;

    minDist = min(minDist, calcDist(P[(mid)], P[mid + 1]));

    fo << fixed;
    fo << setprecision(6) << minDist << "\n";

    fi.close();
    fo.close();

    return 0;
}