Pagini recente » Cod sursa (job #2462948) | Cod sursa (job #2321907) | Cod sursa (job #2065649) | Cod sursa (job #3132215) | Cod sursa (job #1026914)
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
const int NMAX = 100002;
int minDist = NMAX;
int N;
class point{
public:
int x,y;
bool operator <(const point &b){
if(x == b.x){
return y < b.y;
}
else {
return x < b.x;
}
}
}V[NMAX];
int distancePoints(const point &a, const point&b){
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
void swap(point &a, point &b){
point c = a;
a = b;
b = c;
}
void merge(int firstI,int lastI,int firstJ,int lastJ){
int N = lastI - firstI + 1;
int M = lastJ - firstJ + 1;
int i,j,k;
point X[N+1];
point Y[M+1];
for(i = 0; i < N; i++)
X[i] = V[firstI + i];
for(i = 0; i < M; i++)
Y[i] = V[firstJ + i];
X[N].x = X[N].y = Y[M].x = Y[M].y = (1<<30);
for(i = 0, j = 0, k = 0; i < N || j < M;k++){
if(X[i] < Y[j]){
V[firstI + k] = X[i];
i++;
}
else {
V[firstI + k] = Y[j];
j++;
}
}
}
int conquer(int first, int last){
if(last - first < 3){
if(last - first == 2){
if(V[first] < V[first+1] && V[first] < V[first+2]){
if(V[first+2] < V[first+1])
swap(V[first+2],V[first+1]);
}
else if(V[first+1] < V[first] && V[first + 1]<V[first+2]){
swap(V[first], V[first+1]);
if(V[first+2] < V[first+1])
swap(V[first+2],V[first+1]);
}
else if(V[first + 2] < V[first] && V[first+2] < V[first+1]){
swap(V[first],V[first+2]);
if(V[first+2] < V[first+1])
swap(V[first+2],V[first+1]);
}
int d1 = distancePoints(V[first],V[first+1]);
int d2 = distancePoints(V[first],V[first+2]);
int d3 = distancePoints(V[first+1],V[last]);
return min(min(d1,d2),d3);
}
if(last - first == 1){
if(V[first + 1] < V[first])
swap(V[first], V[last]);
return distancePoints(V[first],V[last]);
}
return 0;
}
else {
int middle = (first + last)/2;
int min1 = conquer(first, middle);
int min2 = conquer(middle+1,last);
//interclasez
merge(first,middle,middle+1,last);
minDist = min(minDist,min(min1,min2));
for(int i=first; i <= last; i++){
for(int j = i+1; j <=last && j - i < 8; j++){
minDist = min(minDist, distancePoints(V[i],V[j]));
}
}
return minDist;
}
}
int main()
{
int i;
in >> N;
for(i = 0; i < N; i++){
in >> V[i].x >> V[i].y;
}
out << conquer(0,N-1);
out<<setprecision(20)<<sqrt(minDist);
return 0;
}