Cod sursa(job #1201028)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 24 iunie 2014 12:41:51
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 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];
    k = 0;
    for(i=st; i<=dr; i++)
        if(abs(p[y[i]].x - p[mij].x)<=d)
            aux[++k] = y[i];
    for(i=1; i<k; i++)
        for(j=1; j<8 && i+j<=k; j++){
            dd = dist(p[aux[i]], p[aux[i+j]]);
            if(d>dd) d = dd;
        }
    return d;
}