Cod sursa(job #2303787)

Utilizator cc4infinityCojocaru Catalin cc4infinity Data 16 decembrie 2018 21:18:25
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct coord
{
    int x,y;
};

coord t[100001],v[100001];
int i,j,m,n,x,y;

bool funct(coord a, coord b)
{
    if (a.x>b.x) return 0;
    if (b.x>a.x) return 1;
    if (a.y>b.y) return 0;
    return 1;
}

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

double ds(int a,int b)
{
    double s;
    if (b-a<3)
    {
        if (b-a==1) return dist(t[a],t[b]);
        return min(dist(t[a],t[b]),min(dist(t[a],t[a+1]),dist(t[a+1],t[b])));
    }
    int mid=(a+b)/2,poz=0;
    s=min(ds(a,mid),ds(mid,b));
    for (i=a;i<=b;i++)
      if (abs(t[i].x-t[mid].x)<s) v[++poz]=t[i];
    for (int i=1;i<poz;i++)
          for (j=i+1;j<=poz && j-i<8;j++)
          if (dist(v[i],v[j])<s) s=dist(v[i],v[j]);
    return s;
// practic rezolvat, tu deam fa tabelu v de la a la b parcurgand si vazand ca distanta
// dsa fie mai mica ca s si adauga in v, apoi compara
}

int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>t[i].x>>t[i].y;
    sort(t+1,t+n+1,funct);
    //for (i=1;i<=n;i++)
    //    fout<<t[i].x<<" "<<t[i].y<<"\n";
    fout<<fixed<<setprecision(6)<<ds(1,n);
    return 0;
}