Cod sursa(job #2053754)

Utilizator silkMarin Dragos silk Data 1 noiembrie 2017 11:51:16
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MaxN 100000
#define oo 1LL<<62
#define ll long long
#define x first
#define y second
using namespace std;

typedef pair<int, int> Point;
Point A[MaxN+1];
Point B[MaxN+1];
Point C[MaxN+1];
int N;

bool cmp(const Point A, const Point B)
{
    if(A.y == B.y) return A.x < B.x;
    return A.y < B.y;
}

ll dist(Point A, Point B)
{
    return 1LL * (A.x - B.x) * (A.x - B.x) + 1LL * (A.y - B.y) * (A.y - B.y);
}

ll Solve(int st, int dr)
{
    if(st >= dr) return oo;
    else if(dr - st == 1){
        if(B[st] > B[dr]) swap(B[st], B[dr]);
        return dist(A[st], A[dr]);
    }

    int i, j, k = 0, mid = (st + dr) / 2;
    ll res;

    res = min(Solve(st, mid), Solve(mid+1, dr));
    merge(B + st, B + mid + 1, B + mid + 1, B + dr + 1, C, cmp);
    for(i = st; i <= dr; ++i) B[i] = C[i-st];
    for(i = st; i <= dr; ++i)
        if((B[i].x - A[mid].x) * (B[i].x - A[mid].x) <= res) C[++k] = B[i];

    for(i = 1; i < k; ++i)
        for(j = i+1; j <= k && j - i <= 8; ++j)
        res = min(res, dist(C[i], C[j]));

    return res;
}

int main(){
    FILE* fin = fopen("cmap.in","r");
    FILE* fout = fopen("cmap.out","w");

    int i;

    fscanf(fin,"%d",&N);
    for(i = 1; i <= N; ++i) fscanf(fin,"%d %d",&A[i].x,&A[i].y);

    sort(A+1,A+N+1);
    for(i = 1; i <= N; ++i) B[i] = A[i];
    fprintf(fout,"%f\n",sqrt(Solve(1,N)));


return 0;
}