当前位置:编程学习 > C/C++ >>

poj2420A Star not a Tree? 费马点

[cpp] 
题目意思:求平面上存在的一点到多边形的各个顶点的距离和最小,即费马点。 
 
//0ms 
 
#include<cstdio> 
#include<iostream> 
#include<math.h> 
#define eps 1e-8 
using namespace std; 
 
const int maxn=120; 
struct point{double x,y;}points[maxn],st; 
int dir[4][2]={1,0,0,1,-1,0,0,-1}; 
int n; 
 
double dis(point p1,point p2) 

    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 

double alldis(point tmp) 

    double sum=0; 
    int i; 
    for(i=0;i<n;i++) 
    { 
        sum+=dis(tmp,points[i]); 
    } 
    return sum; 

 
double slove(double step) 

    double minn=1000000000; while(step>0.2) 
    { 
        bool isok=true; 
        while(isok) 
        { 
            int i; 
            isok=false; 
            for(i=0;i<4;i++) 
            { 
                point temp=st; 
                temp.x+=dir[i][0]*step; 
                temp.y+=dir[i][1]*step; 
                double dis=alldis(temp); 
                if(minn>dis) 
                { 
                    isok=true; 
                    minn=dis; 
                    st=temp; 
                } 
                 
            } 
        } 
        step/=2.0; 
    } 
    return minn; 

 
int main() 
{ www.zzzyk.com
    while(~scanf("%d",&n)) 
    { 
        int i; 
        for(i=0;i<n;i++) 
            scanf("%lf%lf",&points[i].x,&points[i].y); 
        st=points[0]; 
        printf("%d\n",(int)(slove(1000)+0.5)); 
    } 
    return 0; 

作者:ssslpk
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,