Cod sursa(job #787143)

Utilizator stefanzzzStefan Popa stefanzzz Data 12 septembrie 2012 18:32:52
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#define MAXN 100005
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

struct punct{
    int x,y;};

int i,j,n;
punct p[MAXN],p1,p2,p3;
double d,mn2;
vector<punct> v;

bool comp1(punct p11,punct p22);
bool comp2(punct p11,punct p22);
double distmin(int a, int b);

int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>p[i].x>>p[i].y;
    sort(p+1,p+n+1,comp1);
    g<<fixed<<setprecision(7)<<distmin(1,n)<<'\n';
    f.close();
    g.close();
    return 0;
}

bool comp1(punct p11,punct p22){
    return p11.x<p22.x;}

bool comp2(punct p11,punct p22){
    return p11.y<p22.y;}

double distmin(int a, int b){
    double mn;
    int mij;
    if(b-a+1==3){
        p1=p[a];
        p2=p[a+1];
        p3=p[b];
        mn=sqrt(double(1LL*(p2.x-p1.x)*(p2.x-p1.x)+1LL*(p2.y-p1.y)*(p2.y-p1.y)));
        d=sqrt(double(1LL*(p2.x-p3.x)*(p2.x-p3.x)+1LL*(p2.y-p3.y)*(p2.y-p3.y)));
        if(d<mn)
            mn=d;
        d=sqrt(double(1LL*(p3.x-p1.x)*(p3.x-p1.x)+1LL*(p3.y-p1.y)*(p3.y-p1.y)));
        if(d<mn)
            mn=d;
        return mn;}
    if(b-a+1==2)
        return sqrt(double(1LL*(p[a].x-p[b].x)*(p[a].x-p[b].x)+1LL*(p[a].y-p[b].y)*(p[a].y-p[b].y)));
    mij=(a+b)/2;
    mn=distmin(a,mij);
    d=distmin(mij+1,b);
    if(d<mn)
        mn=d;
    mn2=mn;
    v.clear();
    for(i=mij;i>=a&&p[mij].x-p[i].x<mn;i--)
        v.push_back(p[i]);
    for(i=mij+1;i<=b&&p[i].x-p[mij].x<mn;i++)
        v.push_back(p[i]);
    sort(v.begin(),v.end(),comp2);
    for(i=0;i<v.size()-1;i++)
        for(j=i+1;j<v.size()&&v[j].y-v[i].y<mn;j++){
            d=sqrt(double(1LL*(v[i].x-v[j].x)*(v[i].x-v[j].x)+1LL*(v[i].y-v[j].y)*(v[i].y-v[j].y)));
            if(d<mn2)
                mn2=d;}
    return mn2;}