Pagini recente » Cod sursa (job #2887710) | Cod sursa (job #2909454) | Cod sursa (job #581222) | Cod sursa (job #326491) | Cod sursa (job #1025623)
#include <fstream>
#include <iomanip>
#include <cmath>
#define epx 0.000001
using namespace std;
struct punct {
int x,y;
};
punct p[100001], y[100001];
int n;
ifstream in("cmap.in");
ofstream out("cmap.out");
void read() {
in>>n;
for (int i = 0; i < n; i++) {
in>>p[i].x>>p[i].y;
}
}
int part(int st, int dr) {
punct aux, pivot;
int i, j;
pivot = p[(st+dr)/2];
i = st-1;
j = dr+1;
while (1) {
do {i++;}while (p[i].x<pivot.x || (p[i].x == pivot.x && p[i].y < pivot.y));
do {j--;}while (p[j].x>pivot.x || (p[j].x == pivot.x && p[j].y > pivot.y));
if (i<j) {
aux = p[i];
p[i] = p[j];
p[j] = aux;
} else return j;
}
}
void quicks(int st, int dr) {
int p;
if (st < dr){
p = part(st, dr);
quicks(st, p);
quicks(p+1, dr);
}
}
long long distanta(punct p1, punct p2) {
return (long long) (p1.x - p2.x) * (p1.x - p2.x) + (long long) (p1.y - p2.y) * (p1.y - p2.y);
}
long long solve(int st, int dr) {
if (dr - st + 1 == 3)
{
long long d1, d2, d3;
int sortat;
d1 = distanta(p[st], p[st+1]);
d2 = distanta(p[st+1], p[dr]);
d3 = distanta(p[dr], p[st]);
do {
sortat = 1;
for (int i = st; i < dr; i++) {
if (y[i].y > y[i+1].y) {
swap(y[i], y[i+1]);
sortat = 0;
}
}
} while (!sortat);
return min(d1,min(d2,d3));
}
if (dr - st + 1 == 2) {
if (y[st].y > y[dr].y) {
swap(y[st], y[dr]);
}
return distanta(p[st], p[dr]);
}
int mij = (st+dr)/2;
long long dst, ddr, D;
punct v[dr - st + 2];
dst = solve(st, mij);
ddr = solve(mij + 1, dr);
D = min(dst, ddr);
int k = 0, i, j;
for (i = st, j = mij + 1; i <= mij && j <= dr;) {
if (y[i].y < y[j].y) {
v[++k] = y[i];
i++;
} else {
v[++k] = y[j];
j++;
}
}
for (; i <= mij; i++){
v[++k] = y[i];
}
for (; j <= dr; j++) {
v[++k] = y[j];
}
for (i = 1; i <= k; ++i) {
for (j = i + 1; j <= k && j < 7 + i ; ++j) {
D = min(D, distanta(v[i], v[j]));
}
}
for (i = st, j = 1; i <= dr; i++, j++) {
y[i] = v[j];
}
return D;
}
int main() {
read();
quicks(0, n-1);
for (int i = 0; i < n; i++) {
y[i] = p[i];
}
long long D = solve(0,n-1);
ofstream out("cmap.out");
out<<setprecision(8)<<sqrt(D);
return 0;
}