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
#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; }