 |
|
 |
|
|
|
计算几何
最近点对
最远点对
最近最远点对
//本来最远距离是用旋转卡壳做的，但是效
//果好象不是很好，所以没有帖那个代码。
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define Maxn 50005
int stack[Maxn];
int top;
struct TPoint
{
double x, y;
}point[Maxn];
int index[Maxn];
int indexl;
int cmpx(const void *a, const void *b)
{
TPoint *c = (TPoint *)a;
TPoint *d = (TPoint *)b;
if(c->x < d->x) return -1;
return 1;
}
int cmpy(const void *a, const void *b)
{
int *c = (int *)a;
int *d = (int *)b;
if(point[*c].y < point[*d].y) return -1;
return 1;
}
double dis(TPoint p1, TPoint p2)
{
double px = p1.x - p2.x;
double py = p1.y - p2.y;
return sqrt(px * px + py * py);
}
double min(double a, double b, double c)
{
if(b < a) a = b;
if(c < a) a = c;
return a;
}
double min(double a, double b)
{
if(a < b) return a;
return b;
}
double shortdis(int l, int r)
{
if(l == r) return 0.0;
else if(l == r - 1) return dis(point[l], point[r]);
else if(l == r - 2)
return min(dis(point[l], point[r]), dis(point[l], point[l + 1]), dis(point[r], point[l + 1]));
else
{
int mid = (l + r) >> 1;
double tmp, mindis = min(shortdis(l, mid), shortdis(mid + 1, r));
indexl = 0;
for(int i = l;i <= mid;i++)
if(point[mid + 1].x - point[i].x < mindis && fabs(point[mid + 1].y - point[i].y) < mindis)
index[indexl++] = i;
for(int i = mid + 1;i <= r;i++)
if(point[i].x - point[mid].x < mindis && fabs(point[i].y - point[mid].y))
