poj3714,POJ 3714 raid

// Raid.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
#include
#define MAX_SIZE 100001
#define N MAX_SIZE*2
#define MAX 1e100
#define EPS 0.000001
struct Point{
double x;
double y;
int index;
short set;
}a[N],b[N],c[N]; //a[N] hold the set 1 and set 2 points
inline double min(double x,double y)
{
return x}
inline double dis(Point p,Point q)
{
double x1=p.x-q.x;
double y1=p.y-q.y;
return sqrt(x1*x1+y1*y1);
}
int cmp_x(const void * p, const void * q)
{
double temp=((Point *) p)->x -((Point *)q)->x;
if(temp>0)
return 1;
else if(fabs(temp) return 0;
else
return -1;
}
int cmp_y(const void *p, const void *q)
{
double temp=((Point *)p)->y -((Point *)q)->y;
if(temp>0)
return 1;
else if(fabs(temp) return 0;
else
return -1;
}
//将 数组q 中的数据 按照 y值 的从小到达 合并到 p数组中。
void merge( Point p[],Point q[],int s, int m ,int t)
{
int i,j,k;
for(i=s,j=m+1,k=s;i<=m && j<=t; )
{
if(q[i].y>q[j].y)
{
p[k++]=q[j];
j++;
}
else
{
p[k++]=q[i];
i++;
}
}
while(i<=m)
{
p[k++]=q[i];
i++;
}
while(j<=t)
{
p[k++]=q[j];
j++;
}
}
void displayPointsArray(Point p[],int n)
{
printf("{");
for(int i=0;i {
// printf("(%lf,%lf), ",p[i].x,p[i].y);
printf("(%f,%f), ",p[i].x,p[i].y);
}
printf("}\n");
}
//b值 是按照 y值 排序好的
double closest(Point * a, Point * b,Point * c,int p,int q)
{
//只剩两个点
if(q-p==1)
{
if(a[p].set!=a[q].set) //两个不是同一集合的则计算
return dis(a[p],a[q]);
else
return MAX;
}
//如果只剩下三个点
if(q-p==2)
{
double x1,x2,x3;
if(a[p].set!=a[q].set)
x1=dis(a[p],a[q]);
else
x1=MAX;
if(a[p].set!=a[p+1].set)
x2=dis(a[p],a[p+1]);
else
x2=MAX;
if(a[p].set!=a[q].set)
x3=dis(a[p],a[q]);
else
x3=MAX;
double m=min(x1,x2);
return min(x3,m);
}
//如果大于等于四个点，则需要进行 分而治之 的递归运算。按照 y值 折半分拆
double d1,d2;
int m=(p+q)>>1;
int i,j,k;
for( i=p,j=p,k=m+1;i<=q;i++)
{
if(b[i].index<=m) //index是不会重复的，而且一定是
{
c[j++]=b[i];
}
else
c[k++]=b[i];
}
displayPointsArray(a,q);
displayPointsArray(b,q);
displayPointsArray(c,q);
printf("############\n");
d1=closest(a,c,b,p,m);
d2=closest(a,c,b,m+1,q);
double dm=min(d1,d2);
merge(b,c,p,m,q);
for(i=p,k=p;i<=q;i++)
{
if(fabs(b[i].x-b[m].x) {
c[k++]=b[i];
}
}
displayPointsArray(c,k);
for(i=p;i {
for(j=i+1;j {
if(c[i].set!=c[j].set)
{
double temp=dis(c[j],c[i]);
if(temp dm=temp;
}
}
}
return dm;
}
int main()
{
int pass,n;
double result;
scanf("%d",&pass);
while(pass--)
{
scanf("%d",&n); //每一个集合都有 n 个点
for(int i=0;i {
scanf("%lf",&a[i].x);
scanf("%lf",&a[i].y);
//分为两个集合，之所以将他们合并到一个数组里，是因为这样更方便操作
if(i a[i].set=0;
else
a[i].set=1;
}
//将数组 a 按 x坐标 从小到大排序
qsort(a,n,sizeof(a[0]),cmp_x);
displayPointsArray(a,n*2);
printf("____________\n");
for(int i=0;i {
a[i].index=i; //按 x 排序后的标号（x小 标号小）
}
memcpy(b,a,sizeof(a[0])*n*2);
//数组b 按 y坐标 从小到大排序
qsort(b,n*2,sizeof(b[0]),cmp_y);
result=closest(a,b,c,0,n*2-1);
printf("%.3f\n",result);
}
return 0;
}

Tags: 

延伸阅读