Cod sursa(job #2875161)

Utilizator alexmorosanuMorosanu Alexandru alexmorosanu Data 21 martie 2022 10:30:26
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#define INF 4e18
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    double x,y;
}z;
bool cmp(punct a,punct b)
{
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}
double dist(punct x,punct y)
{
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
vector <punct> v;
double divide(int st,int dr,vector <punct> &a,vector <punct> &b)
{
    if(st>=dr-1)
        return INF;
    if(dr-st==2)
    {
        if(cmp(b[st],b[st+1])==0)
            swap(b[st],b[st+1]);
        return dist(a[st],a[st+1]);
    }
    int mid=(st+dr)/2;
    double sol=min(divide(st,mid,a,b),divide(mid,dr,a,b));
    sort(b.begin()+st,b.begin()+dr,cmp);
    v.clear();
    for(int i=st;i<dr;i++)
        if(abs(b[i].y-a[mid].x)<=sol)
        v.push_back(b[i]);
    for(int i=0;i<v.size()-1;i++)
        for(int j=i+1;j<v.size() && j-i<8;j++)
            sol=min(sol,dist(v[i],v[j]));
    return sol;
}
vector <punct> a,b;
int n,i;
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>z.x>>z.y;
        a.push_back(z);
    }
    sort(a.begin(),a.end(),cmp);
    for(i=0;i<n;i++)
        b.push_back({a[i].y,a[i].x});
    g<<fixed<<setprecision(6)<<sqrt(divide(0,n,a,b));
    return 0;
}