poj 3714 Raid

http://poj.org/problem?id=3714

求平面中给定的2*N个点, 距离最短的两点距离(两个点必须分别属于两个集合)

套用了别人的求平面最短两点距离的模板, 囧

//model start
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
const int N = 200002;
const double MAX = 10e100, eps = 0.00001; //mark!

struct Point {
	double x, y;
	int index;
	short set;
}a[N], b[N], c[N];

inline double min(double p, double q) {
	return p < q ? p : q;
}

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) < eps) {
		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)<eps){
		return 0;
	} else {
		return -1;
	}
}

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;
	}
}

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+1].set != a[q].set) 
			x2 = dis(a[p+1], a[q]);
		else
			x2 = MAX;
		if(a[p].set != a[p+1].set) 
			x3 = dis(a[p], a[p+1]);
		else
			x3 = MAX;
		double m = min(x1, x2);
		return min(m, x3);

	}
	
	int i, j, k, m = (p+q)>>1;
	double d1, d2;
	for(i=p,j=p,k=m+1; i<=q; ++i) {
		if(b[i].index <= m) {
			c[j++] = b[i];
		} else {
			c[k++] = b[i];
		}
	}
	
	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) < dm) {
			c[k++] = b[i];
		}
	}
	
	for(i=p; i<k; ++i) {
		for(j=i+1; j<k&&c[j].y-c[i].y<dm; ++j) {
			if(c[j].set != c[i].set) {
				double temp = dis(c[j], c[i]);
				if(temp < dm) {
					dm = temp;
				}
			}
		}
	}
	return dm;
}  
//model end

int main() {
//freopen("in.txt", "r", stdin);
	int n, i, t;
	double ans;
	scanf("%d",&t);
	while(t--) {
		scanf("%d", &n);
		int mid = n;
		n = n<<1;
		for(i=0; i<n; ++i) {
			scanf("%lf%lf", &a[i].x, &a[i].y);
			if(i < mid)
				a[i].set = 0;
			else
				a[i].set = 1;
		}
		qsort(a, n, sizeof(a[0]), cmp_x);
		for(i=0; i<n; ++i) {
			a[i].index = i;
		}
		memcpy(b, a, sizeof(a[0])*n);
		qsort(b, n, sizeof(b[0]), cmp_y);
		ans = closest(a, b, c, 0, n-1);
		printf("%.3lf/n", ans);
	}
	return 0;
}

求平面中N个点的最短距离的模板

//求平面中N个点, 距离最近的两点的距离
//model start
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
const int N = 100005;
const double MAX = 10e100, eps = 0.00001; //mark!

struct Point {
	double x, y;
	int index;
}a[N], b[N], c[N];

inline double min(double p, double q) {
	return p < q ? p : q;
}

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) < eps) {
		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)<eps){
		return 0;
	} else {
		return -1;
	}
}

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;
	}
}

double closest(Point *a, Point *b, Point *c, int p, int q) {
	if(q-p == 1) {
		return dis(a[p], a[q]);
	}
	if(q-p == 2) {
		double x1 = dis(a[p], a[q]);
		double x2 = dis(a[p+1], a[q]);
		double x3 = dis(a[p], a[p+1]);
		double m = min(x1, x2);
		return min(m, x3);
	}
	
	int i, j, k, m = (p+q)>>1;
	double d1, d2;
	for(i=p,j=p,k=m+1; i<=q; ++i) {
		if(b[i].index <= m) {
			c[j++] = b[i];
		} else {
			c[k++] = b[i];
		}
	}
	
	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) < dm) {
			c[k++] = b[i];
		}
	}
	
	for(i=p; i<k; ++i) {
		for(j=i+1; j<k&&c[j].y-c[i].y<dm; ++j) {
			double temp = dis(c[j], c[i]);
			if(temp < dm) {
				dm = temp;
			}
		}
	}
	return dm;
}  
//model end

int main() {
//freopen("in.txt", "r", stdin);
	int n, i;
	double ans;
	while(scanf("%d", &n) != EOF) {
		for(i=0; i<n; ++i) {
			scanf("%lf%lf", &a[i].x, &a[i].y);
		}
		qsort(a, n, sizeof(a[0]), cmp_x);
		for(i=0; i<n; ++i) {
			a[i].index = i;
		}
		memcpy(b, a, sizeof(a[0])*n);
		qsort(b, n, sizeof(b[0]), cmp_y);
		ans = closest(a, b, c, 0, n-1);
		//ans为距离的最小值
		printf("%.3lf/n", ans);
	}
	return 0;
}