Pagini recente » Cod sursa (job #1932641) | Cod sursa (job #2402421) | Cod sursa (job #1182693) | Cod sursa (job #2436475) | Cod sursa (job #2488083)
#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[], Point sort_y[], 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, sort_y,median);
float dist_right=DEI(sort_x+median, sort_y, n-median);
float d;
if (dist_left<dist_right)
d=dist_left;
else
d=dist_right;
Point interval[n];
int cnt=0;
for(int i=0;i<n;i++)
if(abs(sort_y[i].x-mid_p.x)<d)
{
interval[cnt] = sort_y[i];
cnt++;
}
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("date4.in");
ofstream g("date4.out");
int n;
f>>n;
Point points[n], v[n];
for (int i=0;i<n;i++)
f>>points[i].x>>points[i].y;
for(int i=0;i<n;i++)
{
v[i].x=points[i].x;
v[i].y=points[i].y;
}
qsort(points, n, sizeof(Point), compare_x);
qsort(v, n, sizeof(Point), compare_y);
float dist = DEI(points, v, n);
g<<dist;
return 0;
}