建立信号基站-c#求解-英雄会在线编程题目

看了下这道题,也觉得非常有意思,因此把这道题也写一下。先上题目:

建立信号基站
  • 北京
  • 难 度 等 级:
题目详情

要建立一个信号基站服务n个村庄,这n个村庄用平面上的n个点表示。假设基站建立的位置在(X,Y),则它对某个村庄(x,y)的距离为max{|X – x|, |Y – y|}, 其中| |表示绝对值,我们的目标是让所有村庄到信号基站的距离和最小。

基站可以建立在任何实数坐标位置上,也可以与某村庄重合。

输入

给定每个村庄的位置x[],y[],x,y都是整数,满足:

-1000000000 < x,y < 1000000000

村庄个数大于1,小于101。

输出

所有村庄到信号基站的距离和的最小值。

关于精度:

因为输出是double。我们这样判断对错,如果标准答案是A,你的答案是a,如果|A – a| < 1e-3 我们认为是正确的,否则认为是错误的。

 

样例

假设有4个村庄位置分别为 (1,4) (2,3) (0,1) (1,1)

我们的结果是5。因为我们可以选择(1.5,2.5)来建立信号基站。

bestDistance = max(|1.5-1|, |2.5-4|) + max(|1.5-2|,|2.5-3|) + max(|1.5-0|,|2.5-1|) + max(|1.5-1|,|2.5-1|)

= max(0.5, 1.5) + max(0.5,0.5) + max(1.5,1.5) + max(0.5,1.5)

= 1.5 + 0.5 + 1.5 + 1.5

= 5

 

分析:

直管感觉就是,给一个大的框框,吧这些点全部框进去,那么信号基站的坐标肯定在这个框框中,呵呵。但是具体在哪里呢?

进一步分析,是所有点到这个基站的x轴坐标差,或者y轴坐标差,谁大取谁。

 

这个就看出端倪了,在坐标系中,y=x和y=-x,吧坐标系划分成4个部分,上下两个部分中的点,y到原点的距离大于x到原点距离。因此,这个框框就很容易找到了。

也就是y=x和y=-x,进行平移,形成的这样一个矩形的框框,平移的距离正好就是:x-y和x+y,其中最大值和最小值决定了这个矩形框框的边界,所以,首先,找出最大值和最小值:这样就有了处理过程:

int[] line1 = new int[x.Length];
int[] line2 = new int[x.Length];
for (int i = 0; i < x.Length; i++)
{
line1[i] = x[i] – y[i];
line2[i] = x[i] + y[i];
}
int t = 0;
for (int i = 0; i < line1.Length; i++)
{
for (int j = i + 1; j < line1.Length; j++)
{
if (line1[i] > line1[j])
{
t = line1[j];
line1[j] = line1[i];
line1[i] = t;
}
if (line2[i] > line2[j])
{
t = line2[j];
line2[j] = line2[i];
line2[i] = t;
}
}
}

首先求出值,然后排下序。这里为了简单,就使用的是冒泡排序法。当然你也可以使用高效点的排序方法。

这里忘了说明一点:就是我们刚才直管感觉,基站落在这个矩形里面,为什么?大家自己分析下吧。这个很容易证明,矩形之外的点到矩形里面的点的值肯定要大。

 

其实这个分析过程,也有助于进行第二步的分析,即找到基站的坐标位置。

首先,在矩形的一边上取某点,然后,沿着y=x的方向移动,我们会发现,当移动到此点所在的y=x+k时,这条直线划分的点在上下两边一样多的时候,距离值最小(自己可以很简单的就证明了)

同理,当点移动到y=k-x直线,划分的上下两边点相同时,距离最短,

 

有了这个分析,我们就是求k1和k2了

double line1K = 0;
double line2K = 0;
if (x.Length % 2 == 1)
{
line1K = line1[line1.Length / 2];
line2K = line2[line2.Length / 2];
}
else
{
line1K = (line1[line1.Length / 2 – 1] + line1[line1.Length / 2 ])/2;
line2K = (line2[line2.Length / 2 – 1] + line2[line2.Length / 2]) / 2;
}

求出了k1,k2,那么这两条直线的交叉点就是基站的坐标点了。

double x1 = (line1K + line2K) / 2;
double y1 = (line2K – line1K) / 2;

剩下就是把距离求出来了。

这个抛出个问题:基站的位置是不是就一定是交叉点?显然不是,当点的个数为偶数时,其实,基站的位置是最里面的四个点围成的矩形。

 

至此,全部完成,提交,ok,没问题。

标签