Pagini recente » Cod sursa (job #1693571) | Cod sursa (job #2150426) | Cod sursa (job #2402291) | Cod sursa (job #365883) | Cod sursa (job #2150434)
#include <stdio.h>
#include <stdlib.h>
#define NMax 100003
#define INF 0x3f3f3f3f
#define INFll 1e18
#define ll long long
typedef struct{
int x;
int y;
}POINT;
typedef struct{
int dist;
int pointX;
int pointY;
}SEGMENT;
POINT a[NMax],b[NMax];
int n;
ll ANS = INFll;
void merge_sort(POINT a[], int lo, int hi); ///dupa x
void swap(POINT *x, POINT *y);
ll min(ll x, ll y);
ll dist2(POINT x, POINT y);
POINT aux[NMax];
POINT aux2[NMax];
ll solve(int lo, int hi){
if(lo == hi){
return INFll;
}
if(hi - lo == 1){
if(b[lo].y > b[hi].y){
swap(&b[lo],&b[hi]);
}
return dist2(a[lo],a[hi]);
}
int mid = (lo + hi) / 2;
ll local_mn = min(solve(lo, mid),solve(mid + 1, hi));
int nr = 0;
int l = lo, r = mid + 1;
while(l <= mid && r <= hi){
if(b[l].y < b[r].y){
aux[++nr] = b[l];
++l;
}else{
aux[++nr] = b[r];
++r;
}
}
while(l <= mid){
aux[++nr] = b[l];
++l;
}
while(r <= hi){
aux[++nr] = b[r];
++r;
}
for(int i = lo, j = 1; i <= hi; ++i){
b[i] = aux[j++];
}
int nr2 = 0;
for(int i = lo; i <= hi; ++i){
if(llabs(1LL*b[i].x - a[mid].x) <= local_mn){
aux2[++nr2] = b[i];
}
}
for(int i = 1; i <= nr2; ++i){
for(int j = i + 1; j <= nr2 && j < i + 8; ++j){
local_mn = min(1LL*local_mn,1LL*dist2(aux2[i],aux2[j]));
}
}
return local_mn;
}
int main(){
FILE *f,*g;
f = fopen("cmap.in","r");
g = fopen("cmap.out","w");
fscanf(f,"%d",&n);
for(int i = 1; i <= n; ++i){
fscanf(f,"%d%d",&a[i].x, &a[i].y);
}
merge_sort(a, 1, n);
for(int i = 1; i <= n; ++i){
b[i].x = a[i].x;
b[i].y = a[i].y;
}
ll ans = solve(1, n);
fprintf(g,"%.8f\n",sqrt(ans));
return 0;
}
POINT v[NMax];
void merge_sort(POINT a[], int lo, int hi){
if(lo == hi){
return;
}
int mid = (lo + hi) / 2;
merge_sort(a, lo, mid);
merge_sort(a, mid + 1, hi);
int nr = 0;
int l = lo, r = mid + 1;
while(l <= mid && r <= hi){
if(a[l].x < a[r].x){
v[++nr] = a[l];
++l;
}else{
v[++nr] = a[r];
++r;
}
}
while(l <= mid){
v[++nr] = a[l];
++l;
}
while(r <= hi){
v[++nr] = a[r];
++r;
}
for(int i = lo, t = 1; i <= hi; ++i){
a[i] = v[t++];
}
}
void swap(POINT *x, POINT *y){
POINT aux = *x;
*x = *y;
*y = aux;
}
ll min(ll x, ll y){
if(x < y)
return x;
return y;
}
ll dist2(POINT x, POINT y){
return 1LL*(1LL*x.x - y.x) * (1LL*x.x - y.x) + 1LL*(1LL*x.y - y.y) * 1LL*(1LL*x.y - y.y);
}