输油管道问题和邮局选址问题

简介: 点到直线距离:Ax+By+C=0坐标(Xo,Yo),那么这点到这直线的距离就为:│AXo+BYo+C│/√(A2+B2),刚开始一直以为要减一,把直线一般公式记成了Ax+By+C=1。   >邮局选址问题和这个一样,只不过xy都要划分。(原来采用分治法求中位数)

点到直线距离:Ax+By+C=0坐标(Xo,Yo),那么这点到这直线的距离就为:│AXo+BYo+C│/√(A2+B2),刚开始一直以为要减一,把直线一般公式记成了Ax+By+C=1。

 

<<问题描述:某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。

 

<<给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。

示例:若n=5,各油井坐标分别为:(1,2),(2,2),(1,3),(3,-2),(3,3),主管道的最优位置的y坐标为2,各油井到主管道之间的输油管道最小长度总和为6。

主管道是东西向的。

这个和邮局选址问题是一类,想想到两点间距离之和最短的点一定在两点之间的线段上,而且是定值,所以邮局选址只需要求出最小和,地址有很多,只要在那个区间就好。

<<下面是一段网友的分析:

如果只有一口井,那么显然是越近越好啦 如果有两口井,那么显然是有以下三种情况: 1.两口井都在主管道北边,那么这个时候的两个连接管道的长度和肯定大于两口井的Y坐标之差 2.两口井都在主管道南边,和情况1是一样的 3.两口井,一个在主管道南边,一个在主管道北边,那么两个连接管道的长度和就等于两口井的Y坐标之差 显然情况三是所要的最短管道的设计情况 就是当主管道在两口井之间的任意位置时,连接管道长度之和都等于两口井的Y坐标之差,是最短的长度 那么将这个结论推广,当有n口井的时候, 1.n是偶数 只要这n口井分布在主管道的两边,一边n/2个,那么就是距离之和最小的 2.n是奇数 只要将这n个井中,Y坐标最中间的(也就是Y是中值的那个)井不算,其余的偶数个井分布在主管道的两侧,这个时候移动主管道,那么这n个连接管道长度之和就决定于那个没有算的井了,因为其余的井的距离之和是固定了的,这个时候只要主管道最接近那个点就好了呀(http://blog.csdn.net/hengjie2009/article/details/7338406)。

 

 1 //可以根据“第k小元素的算法” 算中位数,那样不必排序 
 2 #include <iostream> 
 3 #include <algorithm> 
 4 using namespace std; 
 5  
 6 bool cmp(int a, int b) 
 7 { 
 8     if(a < b) 
 9         return true; 
10     else 
11         return false; 
12 } 
13 int cal(int str[], int n) 
14 { 
15     int mid = 0;
16     int sum = 0;
17     if(n&1)
18         mid = str[n/2];
19     else
20         mid = (str[n/2] + str[n/2-1])/2;
21     for(int i = 0; i < n; i++) 
22         sum += abs(str[i] - mid); 
23     return sum; 
24 } 
25 int main() 
26 { 
27     int x,y[100000]; 
28     int i, n; 
29     while(cin>>n) 
30     { 
31         //x坐标无用,可以直接 scanf("%*d%d",y+i),或者两次都存入数组y 
32         for(i = 0; i < n; i++) 
33             scanf("%d%d",&x,y + i); 
34         sort(y, y + n, cmp); 
35         printf("%d\n",cal(y,n)); 
36     } 
37     return 0; 
38 }

>>邮局选址问题和这个一样,只不过xy都要划分。(原来采用分治法求中位数)

目录
相关文章
|
机器学习/深度学习 传感器 供应链
【优化选址】基于遗传算法实现发件中心-配送点-客户三级选址问题求解附matlab代码
【优化选址】基于遗传算法实现发件中心-配送点-客户三级选址问题求解附matlab代码
【分治法】邮局选址问题
【分治法】邮局选址问题
567 0
【分治法】邮局选址问题
|
存储 物联网 网络性能优化
一文教你小区如何自建快递柜
共享快递拟收费事件后,国内小区物业开启一波自建快递柜的浪潮,阿里平台快递柜销量暴涨1400%。那么问题来了,企业如何基于阿里云物联网平台快速构建一套高可用的共享快递柜服务?
478 12
一文教你小区如何自建快递柜
|
机器学习/深度学习 算法 计算机视觉
【无人机协同】无人飞行器协同车辆实现物资配送问题附matlab代码
【无人机协同】无人飞行器协同车辆实现物资配送问题附matlab代码
|
开发者
邮局选址——DP
题目描述 有n个村庄分布在一条直线上,每个村庄可以用一个坐标xi来进行描述。现在,你需要建设m个邮局,使得每个村庄到离它最近的邮局的距离之和最小。
208 0