HDU 3694 Fermat Point in Quaddrangle(数学-フェ馬点)
3386 ワード
転送ゲート:http://acm.hdu.edu.cn/showproblem.php?pid=3694
四点をあげます.彼らのフェマポイントをお願いします.
この4つの点が凸多角形であれば、対角線の交点であり、その時の多角形が凹んでいる時に、フェマ点が凹んでいる点であることが分かります.
ACコード:
Acceepted
3694
0 MS
344 K
2985 B
G++
XH_Revenn
四点をあげます.彼らのフェマポイントをお願いします.
この4つの点が凸多角形であれば、対角線の交点であり、その時の多角形が凹んでいる時に、フェマ点が凹んでいる点であることが分かります.
ACコード:
Acceepted
3694
0 MS
344 K
2985 B
G++
XH_Revenn
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <cfloat>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d
",a)
#define pi2(a,b) printf("%d %d
",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=6;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;
struct point
{
double x, y;
}p[N],res[N];
struct Line
{
double a,b,c;
};
bool mult(point sp, point ep, point op)
{
return (sp.x - op.x) * (ep.y - op.y) >= (ep.x - op.x) * (sp.y - op.y);
}
bool operator < (const point &l, const point &r)
{
return l.y < r.y || (l.y == r.y && l.x < r.x);
}
double dis(point a,point b)//
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int tubao(point pnt[], int n)
{
int i, len, top = 1;
sort(pnt, pnt + n);
if (n == 0) return 0;
res[0] = pnt[0];
if (n == 1) return 1;
res[1] = pnt[1];
if (n == 2) return 2;
res[2] = pnt[2];
for (i = 2; i < n; i++)
{
while (top && mult(pnt[i], res[top], res[top-1]))
top--;
res[++top] = pnt[i];
}
len = top; res[++top] = pnt[n - 2];
for (i = n - 3; i >= 0; i--)
{
while (top!=len && mult(pnt[i], res[top], res[top-1])) top--;
res[++top] = pnt[i];
}
return top; // ,
}
Line get_Line(point p1,point p2)//
{
Line tmp;
tmp.a=p1.y-p2.y;
tmp.b=p2.x-p1.x;
tmp.c=p1.x*p2.y-p2.x*p1.y;
return tmp;
}
point Line_Line(Line m1, Line m2)//
{
point tmp;
tmp.x=(m1.b*m2.c-m2.b*m1.c)/(m1.a*m2.b-m2.a*m1.b);
tmp.y=(m1.c*m2.a-m2.c*m1.a)/(m1.a*m2.b-m2.a*m1.b);
return tmp;
}
double xiaohao(point t)
{
double sum=0;
forb(i,0,4)
sum+=dis(t,p[i]);
return sum;
}
int main()
{
while(scanf("%lf%lf",&p[0].x,&p[0].y))
{
if(p[0].x<0) break;
for(int i=1;i<4;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
int n=tubao(p,4);
if(n==4)//
{
Line l1=get_Line(res[0],res[2]),l2=get_Line(res[1],res[3]);
point t=Line_Line(l1,l2);
double sum=xiaohao(t);
printf("%.4f
",sum);
}
else//
{
double mi=xiaohao(p[0]);
for(int i=1;i<4;i++)
mi=min(mi,xiaohao(p[i]));
printf("%.4f
",mi);
}
}
return 0;
}