Cod sursa(job #1302498)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 26 decembrie 2014 23:11:45
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#define NMax 100001
#define INF 2000000000
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n, i, j;
struct punct
{
    int x;
    int y;
}point[NMax], tmp[NMax], midpoint[NMax];
bool cmp(const punct &p1, const punct &p2)
{
    return p1.x < p2.x;
}
double dist(punct p1, punct p2)
{
    return sqrt((double)((long long)((long long)p1.x-p2.x)*(p1.x-p2.x)+(long long)((long long)p1.y-p2.y)*(p1.y-p2.y)));
}
double divimp(int st, int dr)
{
    int mid=(st+dr)/2;
    if (st>=dr)
        return INF;
    if (dr-st == 1) {
        if (point[st].y > point[dr].y) {
            swap (point[st], point[dr]);
            punct tm;
            tm=point[st];
            point[st]=point[dr];
            point[dr]=tm;
        }
        return dist(point[st], point[dr]);
    }
    int midlane=point[mid].x;
    double d_st=divimp(st, mid);
    double d_dr=divimp(mid+1, dr);
    double dmin=min(d_st, d_dr);
    int ind=0, ind1, ind2;
    for (ind1=st, ind2=mid+1; ind1 <= mid && ind2 <= dr; ) {
        if (point[ind1].y < point[ind2].y)
            tmp[++ind]=point[ind1++];
        else
            tmp[++ind]=point[ind2++];
    }
    for (; ind1<=mid ; ind1++)
        tmp[++ind]=point[ind1];
    for (; ind2<=dr; ind2++)
        tmp[++ind]=point[ind2];
    int k=0;
    ind=0;
    for (i=st; i<=dr; i++) {
        point[i]=tmp[++ind];
        if (abs(midlane-point[i].x) <= dmin)
            midpoint[++k]=point[i];
    }
    double Min=INF;
    for (i=1; i<=k; i++)
        for (j=i-1; j>=i-6 && j > 0; j--)
            Min = min(Min, dist(midpoint[i], midpoint[j]));
    return min(Min, dmin);
}
int main()
{
    f>>n;
    for (i=1; i<=n; i++)
        f>>point[i].x>>point[i].y;
    sort (point+1, point+n+1, cmp);
    double sol=divimp(1, n);
    g<<fixed<<setprecision(6)<<sol;
    return 0;
}