Cod sursa(job #1494605)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 1 octombrie 2015 15:51:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <climits>
#define w 100001
#define x first
#define y second
using namespace std;
typedef pair<int,int> ret;
ret p[w];
ret q[w];
float dist(ret a,ret b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
float mind=INT_MAX,mini;
void piv(int st, int dr)
{
    if (dr-st<=3)
    {
        if (dr-st+1==3)
        {
            mind=min(mind,dist(p[st],p[dr]));
            mind=min(mind,dist(p[st+1],p[dr]));
            mind=min(mind,dist(p[st],p[st+1]));
        }
        else
            if(dr-st+1==2)
            {
                mind=min(mind,dist(p[st],p[dr]));
            }
    }
    else
    {
        int mij=(p[st].x+p[dr].x)/2,i;
        for (i=st;i<=dr&&p[i].x<=mij;i++);
        piv(st,i-1);piv(i,dr);
    }
}
void pic(int st, int dr)
{
    if (st<dr)
    {
        int mij=(p[st].x+p[dr].x)/2,i,sf,j;
        for (i=st;i<=dr&&p[i].x<=mij-mini;i++);
        sf=0;
        for(;i<=dr&&p[i].x<=mij+mini;i++)
        {
            q[++sf]=p[i];
        }
        //sort(q+1,q+sf+1);
        if (sf<=7)
        {
            for (i=1;i<sf;i++)
                for (j=i+1;j<=sf;j++)
                {
                    mind=min(mind,dist(p[i],p[j]));
                }
        }
        else
        {
            int y=sf/7,ii;
            for (ii=1;ii<=y;ii++)
            {
                for (i=(ii-1)*7;i<7*ii;i++)
                    for (j=i+1;j<=7*ii;j++) mind=min(mind,dist(p[i],p[j]));
            }
            for (i=y*7;i<sf;i++)
                    for (j=i+1;j<=sf;j++) mind=min(mind,dist(p[i],p[j]));
        }
        for (i=st;i<=dr&&p[i].x<=mij;i++);
        pic(st,i-1);pic(i,dr);
    }
}
int main()
{
for (i=st;i<=dr&&p[i].x<=mij-mind;i++);    ifstream f("cmap.in");
    ofstream g("cmap.out");
    int n,i;
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>p[i].x>>p[i].y;
    }
    sort(p+1,p+n+1);
    piv(1,n);
    mini=mind;
    pic(1,n);
    int m=int(mind),h=0;
    while (m!=0)
    {
        h++;
        m/=10;
    }
    g<<setprecision(h+6)<<mind<<'\n';
    f.close();
    g.close();
    return 0;
}