HD-ACM算法专攻系列（15）——Quoit Design

╰半夏微凉° 2021-12-20 16:13 162阅读 0赞

问题描述：

![1173678-20170625112958179-1455226375.png][]

![1173678-20170625113027788-1788277190.png][]

源码：

经典问题——最近邻问题，标准解法

#include"iostream"
    #include"algorithm"
    #include"cmath"
    using namespace std;
    
    struct Point
    {
    	double x;
    	double y;
    };
    
    Point S[100000];//不使用全局变量可能会超内存
    
    bool cmpPointX(Point a, Point b)
    {
    	return a.x > b.x;
    }
    
    bool cmpPointY(Point a, Point b)
    {
    	return a.y > b.y;
    }
    
    double EfficientClosestPair(Point *P, Point *Q, int start, int n)
    {
    	if(n <= 3)
    	{
    		double result;
    		result = (P[start].x - P[start+1].x)*(P[start].x - P[start+1].x) + (P[start].y - P[start+1].y) * (P[start].y - P[start+1].y);
    		if(n == 3)
    		{
    			double tmp = (P[start].x - P[start+2].x)*(P[start].x - P[start+2].x) + (P[start].y - P[start+2].y) * (P[start].y - P[start+2].y);
    			if(tmp < result)result = tmp;
    			tmp = (P[start+1].x - P[start+2].x)*(P[start+1].x - P[start+2].x) + (P[start+1].y - P[start+2].y) * (P[start+1].y - P[start+2].y);
    			if(tmp < result)result = tmp;
    		}
    		return result;
    	}
    	else
    	{
    		int half = n / 2;
    		double d1 = EfficientClosestPair(P, Q, start, half);
    		double d2 = EfficientClosestPair(P, Q, start + half, n - half);
    		double d = d1 < d2 ? d1 : d2;
    		double m = P[start + half - 1].x;
    		int count = 0;
    		double tmp;
    		for(int i = start; i < start + n; i++)
    		{
    			tmp = Q[i].x - m;
    			if(tmp < 0)tmp = - tmp;
    			if(tmp < d)count++;
    		}
    		double dminsq = d;
    		if(count > 1)
    		{
    			//Point *S = new Point[count];
    			for(int i = start, j = 0; i < start + n; i++)
    			{
    				tmp = Q[i].x - m;
    				if(tmp < 0)tmp = - tmp;
    				if(tmp < d)
    				{
    					S[j].x = Q[i].x;
    					S[j].y = Q[i].y;
    					j++;
    				}
    			}
    			int k;
    			for(int i = 0; i < count - 1; i++)
    			{
    				k = i + 1;
    				while(k < count && (S[k].y - S[i].y)*(S[k].y - S[i].y) < dminsq)
    				{
    					dminsq = min((S[k].x - S[i].x)*(S[k].x - S[i].x) + (S[k].y - S[i].y)*(S[k].y - S[i].y), dminsq);
    					k++;
    				}
    			}
    		}
    		
    		return dminsq;
    		
    	}
    }
    
    int main()
    {
    	int n;
    	Point *P, *Q;
    	cout.precision(2);
    	cout.setf(ios::fixed);
    	P = new Point[100000];
    	Q = new Point[100000];
    	while(scanf("%d", &n) != EOF)
    	{
    		if(n == 0)break;
    		for(int i = 0; i < n; i++)
    		{
    			scanf("%lf %lf", &P[i].x,&P[i].y);
    			Q[i].x = P[i].x;
    			Q[i].y = P[i].y;
    		}
    		if(n <= 3)
    		{
    			cout<<sqrt(EfficientClosestPair(P, Q, 0, n)) / 2<<endl;
    		}
    		else
    		{
    			sort(P, P+n, cmpPointX);//使用qsort可能会超时
    			sort(Q, Q+n, cmpPointY);
    			cout<<sqrt(EfficientClosestPair(P, Q, 0, n)) / 2<<endl;
    		}
    	}
        return 0;
    }

转载于:https://www.cnblogs.com/forcheng/p/7634885.html

[1173678-20170625112958179-1455226375.png]: /images/20211220/36c848d25c8943278e5541b533752604.png
[1173678-20170625113027788-1788277190.png]: /images/20211220/3eb2677143904467a1197a83cbbb0364.png