Pagini recente » Cod sursa (job #1132627) | Cod sursa (job #2557088) | Cod sursa (job #260193) | round1 | Cod sursa (job #2984125)
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF 999999999999999999
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct {
long long x, y;
};
unsigned long long dist(punct a, punct b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool comp(punct a, punct b) {
if (a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
int N;
vector <punct> v, o;
void read() {
fin >> N;
punct a;
for (int i = 0; i < N; ++i) {
fin >> a.x >> a.y;
v.push_back(a);
o.push_back(a);
}
sort(v.begin(), v.end(), comp);
sort(o.begin(), o.end(), comp);
}
vector<punct> interclasare(int left, int mid, int right) {
vector<punct> so;
int i = left, j = mid + 1;
while (i <= mid && j <= right) {
if (o[i].y <= o[j].y) {
so.push_back(o[i]);
i++;
}
else {
so.push_back(o[j]);
j++;
}
}
while (i <= mid) {
so.push_back(o[i]);
i++;
}
while (j <= right) {
so.push_back(o[j]);
j++;
}
return so;
}
unsigned long long getdist(int left, int right) {
//special cases
if (right <= left) {
return INF;
}
if (right - left == 1) {
if (o[right].y < o[left].y) {
swap(o[right], o[left]);
}
return dist(v[left], v[right]);
}
//general case
int mid = (right + left) / 2;
unsigned long long dist1 = getdist(left, mid), dist2 = getdist(mid + 1, right);
unsigned long long d = min(dist1, dist2);
vector<punct> so = interclasare(left, mid, right);
int k = 0;
for (int i = left; i <= right; ++i) {
o[i] = so[k];
++k;
}
int r;
for (int i = left; i <= right; ++i) {
r = min(right, i + 7);
for (int j = i + 1; j <= r; ++j) {
d = min(d, dist(o[i], o[j]));
}
}
return d;
}
int main()
{
read();
fout << setprecision(15) << sqrt(getdist(0, N - 1));
return 0;
}