Cod sursa(job #2449770)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 20 august 2019 17:19:09
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include<bits/stdc++.h>
#define Inf 4e18
#define nmax 1000000
using namespace std;

int n;

struct Punct
{
    unsigned long long  x,y;
}P[nmax];

int cmpx(Punct a,Punct b)
{
    if(a.x==b.x) return 0;
    return (a.x>b.x) ? 1: -1;
}

int cmpy(Punct a,Punct b)
{
    if (a.y==b.y) return 0;
    return (a.y>b.y) ? 1: -1;
}


float dist(Punct p1, Punct p2)
{
    return  ((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}

float min(float x,float y)
{
    return (x<y) ? x:y;
}

float brute_force(Punct P[],int n)
{
    float dmin=Inf;
    for(int i=0;i<n;i++)
        for( int j=i+1;j<n;j++)
        if(dmin>dist(P[i],P[j]))
            dmin=dist(P[i],P[j]);
        return dmin;
}

int compareX(const void* a, const void* b)
{
    Punct *p1 = (Punct *)a, *p2 = (Punct *)b;
    if(p1->x == p2->x) return 0;
    return (p1->x > p2->x) ? 1 : -1;
}

int compareY(const void* a, const void* b)
{
    Punct *p1 = (Punct *)a, *p2 = (Punct *)b;
    if(p1->y == p2->y) return 0;
    return (p1->y > p2->y) ? 1 : -1;
}


float closest(Punct P[],int n)
{
    if(n<=3) return brute_force(P,n);
    int mid=n/2;
    Punct Pmid=P[mid];
    float dl=closest(P,mid);
    float dr=closest(P+mid,n-mid-1);
    float  d=min(dl,dr),ans=d;
    Punct adj[n];
    int k=0,i,j;
    for(i=0;i<n;i++)
        if(abs(P[i].x-Pmid.x)<=d)
            adj[k++]=P[i];
    //sort(adj,adj+k-1,cmpy);
    //sortare2(adj,0,k-1);
    qsort(adj,k,sizeof(Punct),compareY);
    //cout<<adj[0].y;
    //demonstrare geometrica (se construieste un cerc din varful a 5 puncte), exista maxim 5 puncte a.y. diferenta coordonatelor lor<=d
    for(i=0;i<k;i++)
        for(j=i+1;j<k && j<=i+6 && (adj[j].y-adj[i].y)<d;j++)
        if(dist(adj[i],adj[j])<d)
            d=dist(adj[i],adj[j]);
            //cout<<d<<' ';
    return d;
}


float solve()
{
    //sort(P,P+n,cmpx);
    //sortare(0,n-1);
    qsort(P,n,sizeof(Punct),compareX);
    //cout<<P[0].x;
    return closest(P,n);
}


int main()
{
    ifstream fin("cmap.in");
    fin>>n;
    for(int i=0;i<n;i++)
        fin>>P[i].x>>P[i].y;
    //sortare(0,n-1);
    fin.close();
    ofstream fout("cmap.out");
    qsort(P,n,sizeof(Punct),compareX);
    float ans=closest(P,n);
    fout<<fixed<<setprecision(10)<<sqrt(ans);
    fout.close();
}