Cod sursa(job #2558080)

Utilizator darisavuSavu Daria darisavu Data 26 februarie 2020 11:49:45
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <math.h>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int x,y;
}a[100005];
int i,n;
int compar(punct a, punct b)
{
    return (a.x<b.x||(a.x==b.x&&a.y<b.y));
}
double dist(int c, int b)
{
    double sol=sqrt((a[c].x-a[b].x)*(a[c].x-a[b].x)+(a[c].y-a[b].y)*(a[c].y-a[b].y));
    return sol;
}
double divide(int st, int dr)
{
   if(dr-st+1<=3)
   {
       if(dr-st+1==3) return min(dist(st,dr),min(dist(st+1,dr),dist(st,st+1)));
       else if(dr-st+1==2) return dist(dr,st);
       else return 0;
   }
   else
   {
        int mij=(st+dr)/2;
        return min(divide(st,mij),divide(mij+1,dr));

   }
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,compar);
    double d=divide(1,n);
    g<<fixed<<setprecision(6)<<d;
    return 0;
}