Pagini recente » Cod sursa (job #1264367) | Cod sursa (job #1820542) | Cod sursa (job #1165839) | Cod sursa (job #2969866) | Cod sursa (job #2074117)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define MAX 100000
#define INF 2147483647
using namespace std;
ifstream in ("cmap.in");
ofstream out ("cmap.out");
int n, m;
struct punct
{
int x, y;
} A[MAX], aux[MAX], pct1, pct2;
bool cmp(const punct& a, const punct& b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
bool cmpy(const punct& a, const punct& b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double dist(punct a, punct b)
{
double d1,d2,dist;
d1 = a.x - b.x;
d2 = a.y - b.y;
dist = sqrt(pow(d1, 2)+pow(d2,2));
return dist;
}
double dmin(int left, int right)
{
if (left == right)
return INF;
if (left + 1 == right)
return dist(A[left], A[right]);
int med;
med = (left + right) / 2;
double minL, minR, mem;
minL = dmin (left, med);
minR = dmin (med, right);
mem = min (minL, minR);
m = 0;
for (int i = left; i < right; i++)
if ((A[i].x <= A[med].x && A[i].x + mem >= A[med].x) || (A[i].x >= A[med].x && A[i].x - mem <= A[med].x))
aux[++m] = A[i];
sort (aux + 1, aux + m + 1, cmpy);
int last = 1;
for (int i = 1; i <= m; i++)
{
while (aux[last].y + mem <= aux[i].y)
last++;
for (int j = last; j < i; j++)
{
if (mem >= dist(aux[i], aux[j]))
{
pct1.x = aux[i].x;
pct1.y = aux[i].y;
pct2.x = aux[j].x;
pct2.y = aux[j].y;
mem = dist (aux[i], aux[j]);
}
}
}
return mem;
}
int main()
{
in>>n;
for (int i = 1; i <= n; i++)
in>>A[i].x>>A[i].y;
sort(A + 1, A + n + 1, cmp);
out<<"Distanta minima este: ";
out<<fixed<<setprecision(6)<<dmin(1, n)<<endl;
out<<"Punctele sunt: ("<<pct1.x<<"; "<<pct1.y<<"); ("<<pct2.x<<"; "<<pct2.y<<")"<<endl;
return 0;
}