題目描述：
求四個(gè)點(diǎn)的費(fèi)馬點(diǎn)與這四個(gè)點(diǎn)的距離和。
算法分析：
如果四個(gè)點(diǎn)構(gòu)成凸四邊形，那么費(fèi)馬點(diǎn)在四邊形交點(diǎn)處。
否則費(fèi)馬點(diǎn)一定是其中的某一個(gè)點(diǎn)。
#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
西月弦 閱讀(200)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告