bnuoj 27874 "Center" of [p]erimeter midpoints(计算几何)

http://www.bnuoj.com/bnuoj/problem_show.php?pid=27874

【题意】：

给你一个三角形三个顶点的坐标ABC，三角形各边取一点DEF，将三角形周长平均分割成两部分，求AE，DC，FB是否相交于一点，是，输出交点坐标，否，输出ERROR

【题解】:

几何体，一看就有点慌，就怕它卡精度，以前坑怕了，这里给出思路以及解题过程：

先求出DEF的坐标再说，拿D举例：

D在AB线段上，并满足AC+AD==DB+BC，这里我们可以用二分枚举来枚举出D的坐标

EF点同上

然后，CD与AE的交点O，判断O是不是也同时在BF上，在输出O的坐标，不在输出ERROR

【ACcode】：

  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <math.h>
  5 #include <algorithm>
  6 
  7 using namespace std;
  8 #define eps 1e-12
  9 
 10 
 11 struct Nod
 12 {
 13     double x,y;
 14     Nod(double dx,double dy)
 15     {
 16         x=dx;
 17         y=dy;
 18     }
 19     Nod(){}
 20 }node[10],tp;
 21 
 22 double dis[10];
 23 double x[10],y[10];
 24 double xx[10],yy[10];
 25 
 26 double distance(int i)
 27 {
 28     return sqrt((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1]));
 29 }
 30 
 31 double distance(double x1,double y1,double x2,double y2)
 32 {
 33     return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
 34 }
 35 
 36 Nod bs(int i)  //二分
 37 {
 38     double l=0,r=1,mid;
 39     double tx,ty;
 40     double len1 = dis[i+2];
 41     double len2 = dis[i+1];
 42     while(l<=r)
 43     {
 44         mid=(l+r)/2;
 45         tx=x[i]+mid*(x[i+1]-x[i]);
 46         ty=y[i]+mid*(y[i+1]-y[i]);
 47         double temp1 = distance(tx,ty,x[i],y[i]);
 48         double temp2 = distance(tx,ty,x[i+1],y[i+1]);
 49         if(len1+temp1<len2+temp2)
 50         {
 51             l=mid+eps;
 52         }
 53         else
 54         {
 55             r=mid-eps;
 56         }
 57     }
 58     return Nod(tx,ty);
 59 }
 60 
 61 Nod getPoint(Nod u1,Nod u2,Nod v1,Nod v2)   //已知线段已经有交点，求交点坐标
 62 {
 63     Nod ret=u1;
 64     double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
 65         /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
 66     ret.x+=(u2.x-u1.x)*t;
 67     ret.y+=(u2.y-u1.y)*t;
 68     return ret;
 69 }
 70 
 71 int main()
 72 {
 73     int t,cas=1;
 74     scanf("%d",&t);
 75     while(t--)
 76     {
 77         int i;
 78         for(i=0;i<3;i++)
 79         {
 80             scanf("%lf%lf",&x[i],&y[i]);
 81             x[i+3]=x[i];  //做成循环，后面可以统一处理
 82             y[i+3]=y[i];
 83         }
 84         for(i=0;i<3;i++)
 85         {
 86             dis[i+3]=dis[i]=distance(i);
 87         }
 88         for(i=0;i<3;i++)
 89         {
 90             node[i+3]=node[i] = bs(i);  //这里用二分来获取，周长分割中点
 91         }
 92         tp=getPoint(node[0],Nod(x[2],y[2]),node[1],Nod(x[3],y[3]));  //得到两条线段的交点
 93         double dis1 = distance(node[2].x,node[2].y,x[1],y[1]);  //第三条线段的长度
 94         double dis2 = distance(node[2].x,node[2].y,tp.x,tp.y)+distance(tp.x,tp.y,x[1],y[1]);  //交点到第三条线段端点之和
 95         printf("Case %d: ",cas++);
 96         if(fabs(dis1-dis2)>=1e-7)  //判断距离是否相等
 97         {
 98             printf("ERROR
");
 99         }
100         else
101         {
102             if(fabs(tp.x)<1e-7)  tp.x=0;  //是否为-0
103             if(fabs(tp.y)<1e-7)  tp.y=0;
104             printf("%.6lf %.6lf
",tp.x,tp.y);
105         }
106     }
107     return 0;
108 }