Pagini recente » Cod sursa (job #2069600) | Cod sursa (job #2404235) | Atasamentele paginii Clasament pressure | Cod sursa (job #1779077) | Cod sursa (job #2487647)
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <fstream>
using namespace std;
struct Point {
float x, y;
};
int compare_x(const void* a, const void* b) {
Point* p = (Point*)a;
Point* q = (Point*)b;
if (p->x < q->x)
return -1;
return 1;
}
int compare_y(const void* a, const void* b) {
Point* p = (Point*)a;
Point* q = (Point*)b;
if (p->y < q->y)
return -1;
return 1;
}
float distance(Point a, Point b) {
float dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
return dist;
}
float DEI(Point sort_x[100], int n) {
if (n <= 3) {
float d_min = 500;
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
if (distance(sort_x[i], sort_x[j]) < d_min)
d_min = distance(sort_x[i], sort_x[j]);
}
}
return d_min;
}
int median;
median = n / 2;
Point mid_p = sort_x[median];
float dist_left = DEI(sort_x, median);
float dist_right = DEI(sort_x + median, n-median);
float d;
if (dist_left < dist_right)
d = dist_left;
else d = dist_right;
Point interval[100];
int cnt = 0;
for (int i = 0;i < n;i++)
if (abs(sort_x[i].x - mid_p.x) < d)
interval[cnt++] = sort_x[i];
qsort(interval, cnt, sizeof(Point), compare_y);
for (int i = 0;i < cnt;i++)
for (int j = i + 1;j < cnt && j < i + 8;j++)
if (distance(interval[i], interval[j]) < d)
d = distance(interval[i], interval[j]);
return d;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
Point points[100];
f>> n;
float a, b;
for (int i = 0;i < n;i++) {
f>> a >> b;
points[i].x = a;
points[i].x = b;
}
qsort(points, n, sizeof(Point), compare_x);
float dist = DEI(points, n);
g << dist;
return 0;
}