题目描述:
求四个点的费马点与这四个点的距离和。
算法分析:
如果四个点构成凸四边形,那么费马点在四边形交点处。
否则费马点一定是其中的某一个点。
#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) 编辑 收藏 引用 所属分类:
解题报告