算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
   求四个点的费马点与这四个点的距离和。

算法分析:
   如果四个点构成凸四边形,那么费马点在四边形交点处。
   否则费马点一定是其中的某一个点。

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<complex>
using namespace std;
#define X real
#define Y imag
const double eps = 1e-9;
typedef complex <double> pnt;
pnt p[4];
bool cmp(const pnt &a ,const pnt &b){
    return arg(a-p[0]) < arg(b-p[0]);
}
static double cross(const pnt &a ,const pnt &b) { return imag(conj(a) * b);}
int main(){
    double x1,y1,x2,y2,x3,y3,x4,y4;
    while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4 && x1!=-1.0){
        p[0] = pnt(x1,y1), p[1] = pnt(x2,y2) , p[2] = pnt(x3,y3),p[3] = pnt(x4,y4);
        int s = 0; double ans = -1;
        for(int t = 0; t <4; t++) {
            double v = 0;
            for(int i=0;i<4;i++) if(i!=t)
                v += abs(p[t]-p[i]);
            if(v < ans || ans == -1.0) ans = v;
        }
        for(int i=1;i<4;i++)
            if(Y(p[i]) == Y(p[s]) ? X(p[i]) < X(p[s]) : Y(p[i]) < Y(p[s]))
                s = i;
        swap(p[s],p[0]);
        sort(p+1,p+4,cmp);
        if(cross(p[2]-p[1],p[3]-p[1])>0) {
            double v = abs(p[0] - p[2]) + abs(p[1]-p[3]);
            if(v < ans) ans = v;
        }
        printf("%.4lf\n",ans);
    }
}
posted on 2012-08-03 16:26 西月弦 阅读(181) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理