Pagini recente » Cod sursa (job #2561113) | Cod sursa (job #1213198) | Cod sursa (job #2654503) | Cod sursa (job #2064798) | Cod sursa (job #2728059)
#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;
}