Cod sursa(job #1075129)

Utilizator dd1997Dan Vasile dd1997 Data 8 ianuarie 2014 17:30:08
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream f ("cmap.in");
ofstream g ("cmap.out");

int n, px, py, i, j, b, e, c, p, m;
int x[100000], y[100000];
long double d1, d2, d3, s1, s2, ss, mn;


double ddcmap(int s, int d)
{
    b=-1000000000;
    p=0;
    for(i=0; i<=n; i++)
    {
        p++;
        if(b==-1000000000 && x[i]>=s)
            b=i;
        if(x[i]<=d)
            e=i;
        else
            break;
    }
    if(p<=3)
    {
        if(p==2)
            return ( sqrt( ((double)x[b]-(double)x[e])*((double)x[b]-(double)x[e]) + ((double)y[b]-(double)y[e])*((double)y[b]-(double)y[e]) ) );
        d1 = sqrt( ((double)x[b]-(double)x[e])*((double)x[b]-(double)x[e]) + ((double)y[b]-(double)y[e])*((double)y[b]-(double)y[e]) );
        d2 = sqrt( ((double)x[b+1]-(double)x[e])*((double)x[b+1]-(double)x[e]) + ((double)y[b+1]-(double)y[e])*((double)y[b+1]-(double)y[e]) );
        d3 = sqrt( ((double)x[b]-(double)x[e-1])*((double)x[b]-(double)x[e-1]) + ((double)y[b]-(double)y[e-1])*((double)y[b]-(double)y[e-1]) );
        if(d1 >= d2 && d1 >= d3)
            return d1;
        if(d2 >= d1 && d2 >= d3)
            return d2;
        return d3;
    }
    m= (b+e)/2;
    s1 = ddcmap(b, m);
    s2 = ddcmap(m+1, e);
    for(i=b; i<=m; i++)
    {
        if(x[m]-x[i]<=s1)
        {
            ss=i;
            break;
        }
    }
    mn= 10000000000;
    for(i=ss; i < ss+8; i++)
        for(j=i+1; j<ss+8; j++)
        {
            d1 = sqrt( ((double)x[i]-(double)x[j])*((double)x[i]-(double)x[j]) + ((double)y[i]-(double)y[j])*((double)y[i]-(double)y[j]) );
            if(d<mn)
                mn=d1;
        }
    ss=s1?s2:(s1<s2);
    return mn?ss:(mn<ss);
}


int main()
{
    f >> n;
    for(; c<n; c++)
    {
        f >> px >> py;
        i=0;
        while(x[i]<=px && i<c)
            i++;
        for(j=c; j>i; j--)
        {
            x[j]=x[j-1];
            y[j]=y[j-1];
        }
        x[i]=px;
        y[i]=py;
    }
    g<<ddcmap(x[0]-2, x[n-1]+2);
    return 0;
}