Cod sursa(job #1770123)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 3 octombrie 2016 19:42:01
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define inf 1e9
using namespace std;

ofstream g("cmap.out");

int n, i, j;
double m, s[10005];
struct point{
    double x, y;
}v[10001];

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


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

double Min(int st,int dr)
{
    if (dr==st)
        return inf;
    if (dr==st+1)
        return dist(v[st],v[dr]);

    vector <point> A, B;
    double mn;
    double m = (s[dr] - s[st-1]) / ((dr-st)+1.0);
    int i = st;
    while (v[i].x < m)
        i++;
    double d1, d2;
    d1 = Min(st, i-1);
    d2 = Min(i, dr);
    mn = min(d1,d2);

    int sav = i-1;
    while (m - v[sav].x < mn && sav > 0)
    {
        A.push_back(v[sav]);
        sav--;
    }

    sav = i;
    while (v[sav].x - m < mn && sav <= n)
    {
        B.push_back(v[sav]);
        sav++;
    }



    int j = 0;
    for (i = 0; i < A.size(); i++)
    {
        while (j+1 < B.size() && B[j+1].y>A[i].y)
            j++;

        sav = j;
        while (sav >= 0 && abs(B[sav].y-A[i].y) < mn)
        {
            double x = dist(B[sav],A[sav]);
            if (x<mn)
                mn=x;
            sav--;
        }
        while (j+1 < B.size() && abs(B[j+1].y-A[i].y) < mn)
        {
            j++;
            double x = dist(B[j],A[j]);
            if (x<mn)
                mn=x;
        }
    }

    return mn;
}

int main()
{
    freopen("cmap.in","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lf%lf", &v[i].x, &v[i].y);

    m = s[n] / (n + 0.0);

    sort(v+1,v+n+1,comp);
    for (int i = 1; i <= n; i++)
        s[i]=s[i-1]+v[i].x;

    int i=1;
    while (v[i].x < m)
        i++;

    g<<Min(1,n);


    return 0;
}