变形了的最近点对，关键在于计算距离的时候，如果同类点的话，直接判定为无穷大即可。

其他闲话：

(1)因为一些原因，*暂时用回C++.

(2)好久没刷题，忘记了数组一开始要开最大，多次new和delete，导致超时。

(3) 感觉算法导论的最近点对没有考虑到有多个点都在一条vertical line上的情形。

#include<iostream>
#include<fstream>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;


enum PointTag{Agent=0, Station=1};

const double NaN = (double)(1<<31 - 1);


struct Point{
	double x;
	double y;
	PointTag tag;

	Point(double tx, double ty, PointTag ttag)
	{
		x = tx;
		y = ty;
		tag = ttag;
	}

	Point()
	{
		x = 0;
		y = 0;
	}
};

Point pointSet[2 * 100000 + 2];
Point pointY[2 * 100000 + 2];
Point pointTrip[2 * 100000 + 2];



double Min(double a, double b)
{
	if (a < b)
		return a;
	return b;
}

bool CompX(Point a, Point b){
	return a.x < b.x;
}

bool CompY(Point a, Point b){
	return a.y < b.y;
}

double Distance_Tag(Point a, Point b){
	if (a.tag == b.tag){
		return NaN;
	}

	double distance = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));

	return distance;
}

double ClosestPair_Bru(int left, int right)
{
	if (right - left < 1)
		return NaN;

	double minDis = NaN;

	for (int i = left; i < right-1; i++){
		for (int j = i+1; j < right; j++){
			double dis = Distance_Tag(pointSet[i], pointSet[j]);

			if (dis < minDis)
				minDis = dis;
		}
	}

	return minDis;
}

double ClosestPair_Rec( int left, int right)
{
	int N = right - left + 1;
	
	if (N <= 3)
	{
		return ClosestPair_Bru(left,right);
	}

	//1: Find the middle index of station
	int mid = (right + left) >> 1;
	double midX = pointSet[mid].x;

	double combineMin = NaN;

	//left
	double leftMin = ClosestPair_Rec(left, mid);

	//right
	double rightMin = ClosestPair_Rec(mid+1, right);

	//The minimal distance from the either side
	combineMin = Min(leftMin, rightMin);
	
	

	//Search the points within the strip
	int count = 0;
	for (int i = left; i <= right; i++)
	{
		if (abs(pointSet[i].x - midX) <= combineMin)
		{
			pointTrip[count++] = pointSet[i];
		}
	}

	sort(pointTrip, pointTrip + count, CompY);

	//Search the minimal distance between the pointTrip
	for (int i = 0; i < count-1; i++){
		for (int j = i + 1; j< count && j < i+ 8 ; j++){
			double dis = Distance_Tag(pointTrip[i], pointTrip[j]);
			if (dis < combineMin)
				combineMin = dis;
		}
	}

	return combineMin;
}

int main()
{
	int T;
	scanf("%d", &T);

	for (int k = 0; k < T; k++){
		int N;
		scanf("%d", &N);
		

		//the station
		for (int i = 0; i < N; i++){
			double x;
			double y;
			scanf("%lf", &x);
			scanf("%lf", &y);
			pointSet[i] = Point(x,y, Station);
			//pointY[i] = Point(x, y, Station);
		}
		//the agent
		for (int i = 0; i < N; i++){
			double x;
			double y;
			scanf("%lf", &x);
			scanf("%lf", &y);
			pointSet[i+N] = Point(x, y, Agent);
			//pointY[i+N] = Point(x, y, Agent);
		}

		//get the sortex X point
		sort(pointSet, pointSet + 2*N, CompX);
		//get the sorted Y point
		//sort(pointY, pointY + 2*N, CompY);

		double mindis = ClosestPair_Rec(0, 2*N);


		printf("%.3f\n", mindis);
	}
}

ORACLE 11G 单实例 磁盘文件系统 DG 归档日志删除脚本 基于RED HAT LINUX 5.3 X86 64BIT,布布扣,bubuko.com

ORACLE 11G 单实例 磁盘文件系统 DG 归档日志删除脚本 基于RED HAT LINUX 5.3 X86 64BIT