首页 > 代码库 > POJ 2420 A Star not a Tree? （计算几何-费马点）

POJ 2420 A Star not a Tree? （计算几何-费马点）

2024-07-09 08:46:11   226人阅读

A Star not a Tree?
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3435 Accepted: 1724

Description

Luke wants to upgrade his home computer network from 10mbs to 100mbs. His existing network uses 10base2 (coaxial) cables that allow you to connect any number of computers together in a linear arrangement. Luke is particulary proud that he solved a nasty NP-complete problem in order to minimize the total cable length. 
Unfortunately, Luke cannot use his existing cabling. The 100mbs system uses 100baseT (twisted pair) cables. Each 100baseT cable connects only two devices: either two network cards or a network card and a hub. (A hub is an electronic device that interconnects several cables.) Luke has a choice: He can buy 2N-2 network cards and connect his N computers together by inserting one or more cards into each computer and connecting them all together. Or he can buy N network cards and a hub and connect each of his N computers to the hub. The first approach would require that Luke configure his operating system to forward network traffic. However, with the installation of Winux 2007.2, Luke discovered that network forwarding no longer worked. He couldn‘t figure out how to re-enable forwarding, and he had never heard of Prim or Kruskal, so he settled on the second approach: N network cards and a hub. 

Luke lives in a loft and so is prepared to run the cables and place the hub anywhere. But he won‘t move his computers. He wants to minimize the total length of cable he must buy.

Input

The first line of input contains a positive integer N <= 100, the number of computers. N lines follow; each gives the (x,y) coordinates (in mm.) of a computer within the room. All coordinates are integers between 0 and 10,000.

Output

Output consists of one number, the total length of the cable segments, rounded to the nearest mm.

Sample Input

4
0 0
0 10000
10000 10000
10000 0

Sample Output

28284

Source

Waterloo Local 2002.01.26

题目大意：

求n边形的费马点，即找到一个点使得这个点到n个点的距离之和最小。


解题思路：

三角形也有费马点，三角形费马点是这样定义的：寻找三角形内的一个点，使得三个顶点到该点的距离之和最小。

三角形费马点的做法是：

（1）若有一个角大于120度，那么这个角所在的点就是费马点。

（2）若不存在，那么对于三角形ABC，任取两条边（假设AB、AC），向外做等边三角形得到C‘ 和 A‘  ，那么AA‘ 和CC‘ 的交点就是费马点。


那么对于这题n多边形，我采取的策略完全不同，采用了模拟退火的做法，这种做法相对比较简单，也可以用在求三角形费马点之中。

模拟退火算法就跟数值算法里面的自适应算法相同的道理

（1）定义好步长

（2）寻找一个起点，往8个方向的按这个步长搜索。

（3）如果找到比答案更小的点，那么以这个新的点为起点，重复（2）

（4）如果找不到比答案更小的点，那么步长减半，再尝试（2）

（5）直到步长小于要求的答案的精度就停止。


解题代码：

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

const int offx[]={1,1,0,-1,-1,-1,0,1};
const int offy[]={0,1,1,1,0,-1,-1,-1};
const int maxn=110;
const double eps=1e-2;

struct point{
    double x,y;
    point(double x0=0,double y0=0){x=x0;y=y0;}
    double getdis(point p){
        return sqrt( (x-p.x)*(x-p.x)+(y-p.y)*(y-p.y) );
    }
}p[maxn];

int n;

double getsum(point p0){
    double sum=0;
    for(int i=0;i<n;i++) sum+=p0.getdis(p[i]);
    return sum;
}

void solve(){
    for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
    double ans=getsum(p[0]),step=100;
    point s=p[0],d;
    while(step>eps){
        bool flag=false;
        for(int i=0;i<8;i++){
            d=point(s.x+step*offx[i],s.y+step*offy[i]);
            double tmp=getsum(d);
            if(tmp<ans){
                s=d;
                ans=tmp;
                flag=true;
            }
        }
        if(!flag) step/=2;
    }
    printf("%.0f\n",ans);
}

int main(){
    while(scanf("%d",&n)!=EOF){
        solve();
    }
    return 0;
}





联系
我们