HDU——3694 Fermat Point in Quadrangle （三分套三分或模拟退火）

In geometry the Fermat point of a triangle, also called Torricelli point, is a point such that the total distance from the three vertices of the triangle to the point is the minimum. It is so named because this problem is first raised by Fermat in a private letter. In the following picture, P 0 is the Fermat point. You may have already known the property that: 

Alice and Bob are learning geometry. Recently they are studying about the Fermat Point. 

Alice: I wonder whether there is a similar point for quadrangle. 

Bob: I think there must exist one. 

Alice: Then how to know where it is? How to prove? 

Bob: I don’t know. Wait… the point may hold the similar property as the case in triangle. 

Alice: It sounds reasonable. Why not use our computer to solve the problem? Find the Fermat point, and then verify your assumption. 

Bob: A good idea. 

So they ask you, the best programmer, to solve it. Find the Fermat point for a quadrangle, i.e. find a point such that the total distance from the four vertices of the quadrangle to that point is the minimum.

Input

The input contains no more than 1000 test cases. 

Each test case is a single line which contains eight float numbers, and it is formatted as below: 

x 1 y 1 x 2 y 2 x 3 y 3 x 4 y 4 

x i, y i are the x- and y-coordinates of the ith vertices of a quadrangle. They are float numbers and satisfy 0 ≤ x i ≤ 1000 and 0 ≤ y i ≤ 1000 (i = 1, …, 4). 

The input is ended by eight -1.

Output

For each test case, find the Fermat point, and output the total distance from the four vertices to that point. The result should be rounded to four digits after the decimal point.

Sample Input

0 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1
-1 -1 -1 -1 -1 -1 -1 -1

Sample Output

2.8284
0.0000

题意：找到一个点到四边形四个点的距离最小；

题解：三分套三分，先三分X，再三分Y，找到最小的，一步一步逼近答案，或者模拟退火，找点，好像三分套三分，与模拟退火有一定的关系，上代码：

三分套三分：

#include <iostream>
#include <cmath>
using namespace std;
const double eps=1e-7;
struct hh{
	double x,y;
}point[21];
double checked(double x,double y){//计算距离
	double sum=0;
	for (int i = 0; i < 4;i++){
		sum+=sqrt((x-point[i].x)*(x-point[i].x)+(y-point[i].y)*(y-point[i].y));
	}
	return sum;
}
double check(double x){//三分Y
	double l=0,r=1e4,lm,rm,ans,ansr,ansl;//三分范围，我用的1e4，满足条件不超时即可
	while(r-l>eps){
		lm=l+(r-l)/3;
		rm=r-(r-l)/3;
		ansl=checked(x,lm);
		ansr=checked(x,rm);
		if(ansl<ansr){
			r=rm;
			ans=ansl;
		}
		else{
			l=lm;
			ans=ansr;
		}
	}
	return ans;
}
int main(){
	while(true){
		for (int i = 0; i < 4;i++){
			scanf("%lf%lf",&point[i].x,&point[i].y);
		}
		if(point[0].x<0) break;
		double l=0,r=1e4,lm,rm,ansl,ansr,ans;//三分范围，我用的1e4，满足条件不超时即可
		while(r-l>eps){//三分X
			lm=l+(r-l)/3;
			rm=r-(r-l)/3;
			ansl=check(lm);
			ansr=check(rm);
			if(ansl<ansr){
				r=rm;
				ans=ansl;
			}
			else{
				l=lm;
				ans=ansr;
			}
		}
		printf("%.4f\n",ans);
	}
	return 0;
} 

模拟退火：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAX = 520;
const double eps = 1e-7;
const int mv[4][2]={1,0,-1,0,0,1,0,-1};//上下左右四个方向即可
struct hh{
	double x,y;
}a[MAX],now,tm;
double jisuan(double x,double y){
	double sum=0;
	for (int i = 0; i < 4;i++){
		sum+=sqrt((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y));
	}
	return sum;
}
int main(){
	while(true){
		for (int i = 0; i < 4;i++){
			cin >> a[i].x >> a[i].y;
		}
		if(a[0].x<0) break;
		double ans,tt=1000;
		now.x=0;
		now.y=0;
		bool flag;
		ans=jisuan(0,0);//从0,0开始，注意！！！
		while(tt>eps){
			flag=true;
			while(flag){
				flag=false;
				for (int i = 0; i < 4;i++){//上下左右走
					double xx=now.x+mv[i][0]*tt;
					double yy=now.y+mv[i][1]*tt;
					double w=jisuan(xx,yy);
					if(w<ans){
						ans=w;
						now.x=xx;
						now.y=yy;
						flag=true;
					}
				}
			}
			tt/=1.5;//精度我用的除以1.5，不超时即可，当然要尽可能准确，而且要符合题意
		}
		printf("%.4f\n",ans);
	}
	return 0;
}