Cod sursa(job #2705352)

Utilizator T1raduTaerel Radu Nicolae T1radu Data 12 februarie 2021 14:08:02
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct p
{
    int x,y;
}Punct[100001];
bool cmp(p A, p B)
{
    return ((A.x<B.x) || (A.x==B.x && A.y<B.y));
}
double dist(int x1, int x2, int y1, int y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}
double Distanta(p Punct[], int q, int r)
{
    double D;
    if(r-q+1>3)
    {
        int mij=(q+r)/2;
        D=min(Distanta(Punct,q,mij),Distanta(Punct,mij+1,r));
    }
    else
    {
        double d1,d2,d3;
        switch(r-q+1)
        {
        case 2:
            D=dist(Punct[q].x,Punct[r].x,Punct[q].y,Punct[r].y);
            break;
        case 3:
            d1=dist(Punct[q].x,Punct[q+1].x,Punct[q].y,Punct[q+1].y);
            d2=dist(Punct[q+1].x,Punct[r].x,Punct[q+1].y,Punct[r].y);
            d3=dist(Punct[r].x,Punct[q].x,Punct[r].y,Punct[q].y);
            D=min(d1,min(d2,d3));
            break;
        }
    }
    return D;
}
int n;
int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
        fin >> Punct[i].x >> Punct[i].y;
    sort(Punct+1,Punct+n+1,cmp);
    fout << fixed << setprecision(6) << Distanta(Punct,1,n);
    return 0;
}