Cod sursa(job #1198680)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 16 iunie 2014 17:33:18
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX 100001
const long long INF = 1ll<<62;
struct punct{
    int x, y;
} p[MAX];
int y[MAX], n, aux[MAX];
bool cmp(punct a, punct b){return a.x<b.x;}
long long solve(int st, int dr);
long long dist(punct a, punct b){return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);}
int main()
{
    int i;
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d", &p[i].x, &p[i].y);
        y[i] = i;
    }
    sort(p+1, p+n+1, cmp);
    printf("%f", sqrt((double)solve(1, n)));
    return 0;
}
long long solve(int st, int dr)
{
    int i, j, k;
    long long d, dd;
    if(st+1==dr){
        if(p[st].y>p[dr].y) y[st] = dr, y[dr] = st;
        return dist(p[st], p[dr]);
    }
    if(st==dr) return INF;
    int mij = (st+dr)/2;
    d = solve(st, mij);
    dd = solve(mij+1, dr);
    if(d>dd) d = dd;
    i = st; j = mij+1; k = 0;
    while(i<=mij && j<=dr)
        if(p[y[i]].y<p[y[j]].y) aux[++k] = y[i++];
        else aux[++k] = y[j++];
    while(i<=mij) aux[++k] = y[i++];
    while(j<=dr) aux[++k] = y[j++];
    for(i=st; i<=dr; i++) y[i] = aux[i+1-st];
    for(i=st; i<dr; i++)
        for(j=1; j<8 && i+j<=dr; j++){
            dd = dist(p[i], p[i+j]);
            if(d>dd) d = dd;
        }
    return d;
}