Cod sursa(job #869168)

Utilizator enedumitruene dumitru enedumitru Data 1 februarie 2013 00:49:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
using namespace std; 
const int Nmax = 100010; 
const double inf = 2e+9; 
int n, m; 
struct art {int x, y;} A[Nmax], aux[Nmax]; 
inline int cmpx(const art &A, const art &B) 
{   if (A.x == B.x) return A.y < B.y; 
    return A.x < B.x; 
} 
inline int cmpy(const art &A, const art &B)
{   if (A.y == B.y) return A.x < B.x; 
    return A.y < B.y; 
} 
inline double sqr(double x) {return x * x;} 
inline double dist(const art &A, const art &B) 
{   return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));} 
double solve(int st, int dr)
{   if (st == dr) return inf; 
    if (st + 1 == dr) return dist(A[st], A[dr]); 
    int mid = (st + dr) / 2; 
    double d1 = solve(st, mid);  
    double d2 = solve(mid + 1, dr); 
    double ans = min(d1, d2); 
    m = 0; 
    for (int i = st; i <= dr; i++) 
        if ((A[i].x <= A[mid].x && A[i].x + ans >= A[mid].x) || 
            (A[i].x >= A[mid].x && A[i].x - ans <= A[mid].x)) 
                aux[++m] = A[i]; 
    sort(aux + 1, aux + m + 1, cmpy); 
    int last = 1; 
    for (int i = 1; i <= m; i++) 
	{   while (aux[last].y + ans <= aux[i].y) last++; 
        for (int j = last; j < i; j++) 
            ans = min(ans, dist(aux[j], aux[i])); 
    } 
    return ans; 
} 
int main() 
{   freopen("cmap.in", "r", stdin); freopen("cmap.out", "w", stdout); 
    scanf("%d", &n); 
    for (int i = 1; i <= n; i++) scanf("%d %d", &A[i].x, &A[i].y);
    sort(A + 1, A + n + 1, cmpx); 
    printf("%lf\n", solve(1, n)); 
    return 0; 
}