庞果英雄会——建立信号基站

一、题目分析

分析题目可知，所求解是一个二维空间中的某点。可以参照一维空间中的三分法查找找到最优值。

如下图：最优点一下位于谷底处：

仿照三分法，在空间中找到四个点，依次为0，1，2，3：

计算这个四点的距离值，找出最大值和最小值：

假设红色点是最小值点，绿色为最大值点，可以推断最优点一定在红色点附近，那么就可以将搜索空间缩小，即按黑色箭头指示方向缩小空间，然后重复此过程，直到满足精度要求。

在搜索空间过程中要注意到如果最小值点与最大值点挨着的情况下，按上面的过程缩小空间可能会将最优点去除（第一次就是没有考虑这种情况失败了，修改后通过~_~），所以要判断最小值点与最大值点关系，然后选择缩小空间的方向，如图：

只能向一个方向缩小空间。

二、通过代码

#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#ifdef WIN32
typedef __int64 ll;
#else
typedef long long ll;
#endif

double max(double x, double y)
{
	return x > y ? x : y;
}

double cal(double px, double py, int n, const int *x, const int *y)
{
	double res = 0;

	for(int i = 0; i < n; ++i)
	{
		res += max(fabs(px - x[i]), fabs(py - y[i]));
	}

	return res;
}

int cmp(double *smallest, int *code, double *distance)
{
	int index = 0;
	*smallest = distance[0];
	*code = 0;
	for(int i = 1; i < 4; ++i)
	{
		if(distance[index] < distance[i])
		{
			index = i;
		}
		if(*smallest > distance[i])
		{
			*smallest = distance[i];
			*code = i;
		}
	}

	return index;
}

bool isFinish(double *distance)
{
	bool res = false;

	double sum = 0;
	double delta = 0;
	for(int i = 0; i < 4; ++i)
	{
		sum += distance[i];
	}
	sum /= 4;

	for(int i = 0; i < 4; ++i)
	{
		delta += fabs(sum - distance[i]);
	}

	if(delta / 4 < 1e-4)
	{
		res = true;
	}

	return res;
}

double bestDistance(int n, const int *x,const int *y) 
{
	double xl_down, yl_down;
	double xl_up, yl_up;
	double xr_down, yr_down;
	double xr_up, yr_up;
	double res = 1000000000000000000;
	double cur = 1000000000;

	double xtmp[4];
	double ytmp[4];

	xl_down = -1000000000;
	yl_down = -1000000000;

	xl_up = -1000000000;
	yl_up = 1000000000;

	xr_down = 1000000000;
	yr_down = -1000000000;

	xr_up = 1000000000;
	yr_up = 1000000000;

	double distance[4];
	while(1)
	{
		//上左
		xtmp[0] = xl_up + (xr_up - xl_up) / 3;
		ytmp[0] = yl_up - (yl_up - yl_down) / 3;

		distance[0] = cal(xtmp[0], ytmp[0], n, x, y);

		//上右
		xtmp[1] = xr_up - (xr_up - xl_up) / 3;
		ytmp[1] = yl_up - (yl_up - yl_down) / 3;

		distance[1] = cal(xtmp[1], ytmp[1], n, x, y);

		//下左
		xtmp[2] = xl_down + (xr_down - xl_down) / 3;
		ytmp[2] = yl_down + (yl_up - yl_down) / 3;

		distance[2] = cal(xtmp[2], ytmp[2], n, x, y);

		//下右
		xtmp[3] = xr_down - (xr_down - xl_down) / 3;
		ytmp[3] = yr_down + (yr_up - yr_down) / 3;

		distance[3] = cal(xtmp[3], ytmp[3], n, x, y);

		int s_index;
		int index = cmp(&cur, &s_index, distance);

		if(cur < res)//更新最新的值
		{
			res = cur;
		}

		if(isFinish(distance))//是否达到精度要求
		{
			break;
		}
		switch(index)
		{
		case 0://上左
			if(s_index == 1)
			{
				xl_up = xtmp[0];
				xl_down = xtmp[0];
			}
			else if(s_index == 2)
			{
				yl_up = ytmp[0];
				yr_up = ytmp[0];
			}
			else
			{
				xl_up = xtmp[0];
				yl_up = ytmp[0];

				xl_down = xtmp[0]; 
				yr_up = ytmp[0];
			}
			break;
		case 1://上右
			if(s_index == 0)
			{
				xr_up = xtmp[1];
				xr_down = xtmp[1];
			}
			else if(s_index == 3)
			{
				yr_up = ytmp[1];
				yl_up = ytmp[1];
			}
			else
			{
				xr_up = xtmp[1];
				yr_up = ytmp[1];

				xr_down = xtmp[1];
				yl_up = ytmp[1];
			}
			break;
		case 2://下左
			if(s_index == 0)
			{
				yl_down = ytmp[2];
				yr_down = ytmp[2];
			}
			else if(s_index == 3)
			{
				xl_down = xtmp[2];
				xl_up = xtmp[2];
			}
			else
			{
				xl_down = xtmp[2];
				yl_down = ytmp[2];

				xl_up = xtmp[2];
				yr_down = ytmp[2];
			}
			break;
		case 3://下右
			if(s_index == 1)
			{
				yr_down = ytmp[3];
				yl_down = ytmp[3];
			}
			else if(s_index == 2)
			{
				xr_down = xtmp[3];
				xr_up = xtmp[3];
			}
			else
			{
				xr_down = xtmp[3];
				yr_down = ytmp[3];

				xr_up = xtmp[3];
				yl_down = ytmp[3];
			}
			break;
		default:
			printf("error\n");
		}
	}

	return res;
}


int main()
{
	double res;
	//int n = 4;
 //   int x[] = {1, 2, 0, 1};
 //   int y[] = {4, 3, 1, 1};
	int n = 19; 
	int x[] = {858442934,-161749718,-55910439,347569202,-660170269,-982075453,-860790164,947179323,312298821,-285196111,967545126,-777105315,-630974471,-713895350,745616673,840630174,-597730146,-205693089,24677872};
	int y[] = {449535070,160026431,705809990,121634879,648304545,-392329548,-447666131,-829918127,926665890,943182185,601133076,-848803337,89719473,-586785144,832132969,-111884761,-556530757,65860874,978639057};
	res = bestDistance(n, x, y);
	printf("%f\n", res);
	return 0;
}