Pagini recente » Cod sursa (job #130337) | Cod sursa (job #648046) | Cod sursa (job #2955532) | Cod sursa (job #1049414) | Cod sursa (job #2911642)
#include <bits/stdc++.h>
using namespace std;
int const N = 1e6 + 1;
struct punct
{
double x, y;
} p[N];
inline bool cmp(punct a, punct b);
inline bool cmp_x(punct a, punct b);
inline bool cmp_y(punct a, punct b);
double dist(punct a, punct b)
{
int difx = fabs(a.x - b.x);
int dify = fabs(a.y - b.y);
return sqrt(difx * difx + dify * dify);
}
double aux = INT_MAX;
double divide(int l, int r)
{
if(r - l <= 1)
return INT_MAX;
int mid = (l + r) / 2;
double lx = divide(l, mid);
double rx = divide(mid, r);
aux = min(aux, min(lx, rx)); // fixez lungimea delta
double x_sep = p[mid].x; // x-ul dreaptei d
vector <punct> a;
vector <punct> b;
for(int i = l; i < mid; i++)
{
if(p[i].x >= x_sep - aux)
a.push_back(p[i]);
}
for(int i = mid; i < r; i++)
{
if(p[i].x <= x_sep + aux)
b.push_back(p[i]);
}
// slectam doar ce in deptunghiul delta x 2*delta
sort(a.begin(), a.end(), cmp_y);
sort(b.begin(), b.end(), cmp_y); // sortam dupa y
int pointLeft, pointRight;
pointLeft = pointRight = 0;
double ans = aux;
for(auto pointCurrent: a)
{
while(pointRight < b.size() and b[pointRight].y <= pointCurrent.y + aux) // +delta
{
pointRight ++;
}
while(pointLeft < b.size() and b[pointLeft].y <= pointCurrent.y - aux) // -delta
{
pointLeft ++;
}
if(pointLeft == b.size())
break;
for(int i = pointLeft; i <= pointRight; i ++)
{
ans = min(ans, dist(pointCurrent, b[i]));
}
}
return ans;
}
// v = p
int main()
{
ifstream cin("cmap.in");
ofstream cout("cmap.out");
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> p[i].x >> p[i].y;
}
sort(p + 1, p + n + 1, cmp);
cout << fixed << setprecision(6) << divide(1, n) << "\n";
return 0;
}
inline bool cmp(punct a, punct b)
{
if(a.x == b.x)
return (a.y < b.y);
return (a.x < b.x);
}
inline bool cmp_x(punct a, punct b)
{
return (a.x < b.x);
}
inline bool cmp_y(punct a, punct b)
{
return (a.y < b.y);
}