HDu 3694 Fermat Point in Quadrangle Fe馬点

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3694
4つの点を与えて四角形を構成し(順番に与えない)、フェルマ距離を求める.
1.4つの点しかないので、この4つの点が凸四角形を構成できる場合(図のように):対角線によって形成される交点はフェルマ点である.点1であり、三角形の両側が第3の辺より大きいことによって証明される.
2.凸多角形を構成できない場合、その凹点はフェルマ点(図のように):同じ理屈で証明できる.
コードは以下の通りです://ちょっと見苦しいTT

#include<cstdio>
#include<iostream>
#include<math.h>
#define eps 1e-8
using namespace std;

const int maxn=4;
struct point{double x,y;}points[maxn];
int n=4;

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 xmult(point p1,point p2,point p0)
{
	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
point intersection(point p1,point p2,point p3,point p4)
{
	point ret=p1;
	double t=((p1.x-p3.x)*(p3.y-p4.y)-(p1.y-p3.y)*(p3.x-p4.x))
		/((p1.x-p2.x)*(p3.y-p4.y)-(p1.y-p2.y)*(p3.x-p4.x));
	ret.x+=(p2.x-p1.x)*t;
	ret.y+=(p2.y-p1.y)*t;
	return ret;
}

double min(double a,double b)
{
	return a>b? b:a;
}
int main()
{
	while(1)
	{
		int i;
		for(i=0;i<4;i++)
			scanf("%lf%lf",&points[i].x,&points[i].y);
		if(points[0].x==-1&&points[1].x==-1&&points[2].x==-1&&points[3].x==-1&&
            points[0].y==-1&&points[1].y==-1&&points[2].y==-1&&points[3].y==-1)break;
		
		double res=0;
		double minn=1000000000;
		for(i=0;i<n;i++)
		{
			res=alldis(points[i]);
			minn=min(minn,res);
		}
		if(xmult(points[0],points[1],points[3])*xmult(points[2],points[1],points[3])<0)
		{
			point ans=intersection(points[0],points[2],points[1],points[3]);
			res=alldis(ans);
			minn=min(minn,res);
			
		}
		if(xmult(points[1],points[2],points[3])*xmult(points[0],points[2],points[3])<0)
		{
			point ans=intersection(points[1],points[0],points[2],points[3]);
			res=alldis(ans);
			minn=min(minn,res);
		}
		if(xmult(points[2],points[0],points[3])*xmult(points[1],points[0],points[3])<0)
		{
			point ans=intersection(points[2],points[1],points[0],points[3]);
			res=alldis(ans);
			minn=min(minn,res);
		}
		printf("%.4lf
",minn);
	}
	return 0;
}