Pagini recente » Cod sursa (job #1259123) | Cod sursa (job #2049112)
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdlib>
#include <vector>
#define ld long double
#define pb push_back
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int N = 1e5 + 10;
struct point
{
int x, y;
};
int compx(const void* a, const void* b)
{
point x = *(point*)a;
point y = *(point*)b;
if(x.x - y.x == 0)
return x.y - y.y;
return x.x - y.x;
}
int compy(const void* a, const void* b)
{
point x = *(point*)a;
point y = *(point*)b;
if(x.y - y.y == 0)
return x.x - y.x;
return x.y - y.y;
}
int n;
point p[N];
ld mini = 4e9;
ld points3(int l, int r)
{
vector < ld > dis;
dis.pb(sqrt((p[l].x - p[r].x) * (p[l].x - p[r].x) + (p[l].y - p[r].y) * (p[l].y - p[r].y)));
int i = 1;
while(l++ < r)
{
dis.pb(sqrt((p[l].x - p[l+1].x) * (p[l].x - p[l+1].x) + (p[l].y - p[l+1].y) * (p[l].y - p[l+1].y)));
}
ld minid = min(dis[0], dis[1]);
if(dis.size() == 2) return minid;
else return min(minid, dis[3]);
}
ld solve(int l, int r)
{
if(l + 4 > r)
return points3(l, r);
int mid = (l + r)/2;
mini = min(mini, min(solve(l, mid), solve(mid+1, r)));
for(int i = 0; i < n; ++i)///!
{
for(int j = i; j < n && p[j].y - p[i].y < mini; ++j)
{
for(int ii = i; ii < j; ++i)
{
ld mini2 = sqrt((p[ii].x - p[j].x) * (p[ii].x - p[j].x) + (p[ii].y - p[j].y) * (p[ii].y - p[j].y));
mini = min(mini, mini2);
}
}
}
return mini;
}
int main()
{
//ios::sync_with_stdio(false);
fin >> n;
for(int i = 0; i < n; ++i)
{
fin >> p[i].x >> p[i].y;
}
for(int i = 0; i < n; ++i)
{
cout << p[i].x << " " << p[i].y << "\n";
}
qsort(p, n, sizeof(p), compx);
for(int i = 0; i < n; ++i)
{
cout << p[i].x << " " << p[i].y << "\n";
}
ld mindist = solve(0, n-1);
cout << mindist << "\n";
return 0;
}