Cod sursa(job #2728059)

Utilizator razviOKPopan Razvan Calin razviOK Data 22 martie 2021 19:09:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.61 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <fstream>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
    int abscisa,ordonata;
} puncte[100001];
int N;
bool compareAbscisa(punct a,punct b)
{
    if(a.abscisa==b.abscisa)
        return a.ordonata>b.ordonata;
    else return a.abscisa>b.abscisa;
}
bool compareOrdonata(punct a,punct b)
{
    if(a.ordonata==b.ordonata)
        return a.abscisa>b.abscisa;
    else return a.ordonata>b.ordonata;
}
long long calc_dist(punct a,punct b)
{
    return (a.abscisa-b.abscisa)*(a.abscisa-b.abscisa)+
           (a.ordonata-b.ordonata)*(a.ordonata-b.ordonata);
}
long long bruteForce(punct Points[],int high)
{
    long long mn=4e18;
    for(int i=0; i<high; i++)
        for(int j=i+1; j<high; j++)
            if(calc_dist(Points[i],Points[j])<mn)
                mn=calc_dist(Points[i],Points[j]);
    return mn;
}
long long Closest_to_Line(punct Line[],int length,long long dist)
{
    long long mn=dist;

    for(int i=0; i<length; i++)
        for(int j=i+1; j<length; j++)
        {
            if(Line[j].ordonata-Line[i].ordonata<mn && calc_dist(Line[i],Line[j])<mn)
                mn=calc_dist(Line[i],Line[j]);
        }

    return mn;
}
long long cmap(int high,punct Points_x[],punct Points_y[])
{
    if(high<=3)
        return bruteForce(Points_x,high);

    int mid=high/2;

    punct Points_y_left[mid];
    punct Points_y_right[high-mid];
    int left=0,right=0;

    for(int i=0; i<high; i++)
    {
        if(Points_y[i].abscisa<=Points_x[mid].abscisa && left<mid)
            Points_y_left[left++]=Points_y[i];
        else
            Points_y_right[right++]=Points_y[i];
    }

    long long d_left=cmap(mid,Points_x,Points_y_left);
    long long d_right=cmap(high-mid,Points_x+mid,Points_y_right);

    long long d_min=min(d_left,d_right);

    punct Line[high];
    int j=0;
    for(int i=0; i<high; i++)
        if(abs(Points_y[i].abscisa-Points_x[mid].abscisa)<d_min)
            Line[j++]=Points_y[i];

    return Closest_to_Line(Line,j,d_min);
}
int main()
{
    f>>N;
    for(int i=0; i<N; i++)
        f>>puncte[i].abscisa>>puncte[i].ordonata;      //citim coordonatele celor n puncte


    punct Points_x[N];
    punct Points_y[N];

    for(int i=0; i<N; i++)
    {
        Points_x[i]=puncte[i];
        Points_y[i]=puncte[i];
    }

    sort(Points_x,Points_x+N,compareAbscisa);
    sort(Points_y,Points_y+N,compareOrdonata);

    g<<fixed<<setprecision(6)<<sqrt(cmap(N,Points_x,Points_y));



    return 0;
}