Pagini recente » Cod sursa (job #3188844) | Cod sursa (job #1730273) | Cod sursa (job #292303) | Cod sursa (job #1536611) | Cod sursa (job #2464739)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include<bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define MAX_SIZE 100001
int n, i, j, pos;
double dpos;
double dist, dmin;
struct Punct {
int x, y;
} punct[MAX_SIZE], fpunct[MAX_SIZE], w[MAX_SIZE];
double Dist(int i, int j) {
return sqrt((punct[i].x-punct[j].x)*(punct[i].x-punct[j].x) + (punct[i].y-punct[j].y)*(punct[i].y-punct[j].y));
}
double fDist(int i, int j) {
return sqrt((fpunct[i].x-fpunct[j].x)*(fpunct[i].x-fpunct[j].x) + (fpunct[i].y-fpunct[j].y)*(fpunct[i].y-fpunct[j].y));
}
void msort(int st,int m,int dr)
{
int i=st,j=m+1,k=st-1;
for(; i<=m&&j<=dr;)
{
if(punct[i].y<punct[j].y){
w[++k]=punct[i++];
}
else
w[++k]=punct[j++];
}
while(i<=m){
w[++k]=punct[i++];
}
while(j<=dr){
w[++k]=punct[j++];
}
for(i=st;i<=dr;i++)
punct[i]=w[i];
}
void fmsort(int st,int m,int dr)
{
int i=st,j=m+1,k=st-1;
for(; i<=m&&j<=dr;)
{
if(fpunct[i].y<fpunct[j].y){
w[++k]=fpunct[i++];
}
else
w[++k]=fpunct[j++];
}
while(i<=m){
w[++k]=fpunct[i++];
}
while(j<=dr){
w[++k]=fpunct[j++];
}
for(i=st;i<=dr;i++)
fpunct[i]=w[i];
}
double Recursivitate(int in, int sf) {
int dif = sf-in+1;
int sum = sf+in;
if(dif > 255) {
dmin = min(Recursivitate(in, sum/2), Recursivitate(sum/2+1, sf));
if(dif%2 == 1)
dpos = double(punct[in+dif/2+1].x);
else dpos = double(punct[in+dif/2].x + punct[in+dif+1].x)/2;
pos = 0;
for(i = in; i <= sf; i++) {
if(abs(punct[i].x - dpos) < dmin) {
fpunct[++pos] = punct[i];
}
}
fmsort(in, in+dif/2, sf);
for(i = 1; i < pos; i++) {
for(j = i+1; j <= i+7 && j <= pos; j++) {
dmin = min(dmin, fDist(i, j));
}
}
}
else {
dmin = LONG_MAX;
for(i = in; i < sf; i++)
for(j = i+1; j <= sf; j++)
dmin = min(dmin, Dist(i, j));
}
return dmin;
}
int main()
{
dmin = LONG_MAX;
f >> n;
for(i = 1; i <= n; i++)
f >> punct[i].x >> punct[i].y;
msort(1, n/2, n);
g << fixed << setprecision(6) << Recursivitate(1, n);
return 0;
}