【题目大意】
给定一个凸四边形的三条等长边的中点,求这个四边形的四个顶点坐标
【输入】
第一行一个数字T
接下来T行每行六个数字描述中点的坐标
【输出】
如果存在凸四边形,输出"YES"并在下一行按顺时针或逆时针顺序输出四个点的坐标
如果不存在,输出"NO"并在下一行输出一个空行
首先枚举哪个点是被两条等长边夹住的等长边的中点(xb,yb),另外两个点我们记为(xa,ya),(xc,yc)
然后设这条边的两个顶点(x1,y1),(x2,y2)
我们有
x1+x2=2*xb
y1+y2=2*yb
(x1-xb)^2+(y1-yb)=(x1-xa)^2+(x1-ya)
(x2-xb)^2+(y2-yb)=(x2-xc)^2+(x2-yc)
解方程
然后可以知道四个顶点的坐标
再判下对边是否相交
再判下是不是退化成三角形或者线段或者点
再判下是不是凸多边形
极其蛋疼
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const double eps=1e-7; int t,i,j,k; int x[4],y[4]; double fabs(double x) { if (x>0) return x;else return -x; } double cross(double x1,double y1,double x2,double y2,double x3,double y3) { double u1,v1,u2,v2; u1=x1-x2; v1=y1-y2; u2=x3-x2; v2=y3-y2; return u1*v2-u2*v1; } bool meet(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4) { double u1,v1,u2,v2,u3,v3; u1=x1-x2; v1=y1-y2; u2=x3-x2; v2=y3-y2; u3=x4-x2; v3=y4-y2; return (u1*v2-u2*v1)*(u1*v3-u3*v1)<eps; } bool solve(int a,int b,int c) { if ((x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])==0) return false; double a1,a2,b1,b2,c1,c2,x1,x2,y1,y2; a1=2*(x[a]-x[b]); b1=2*(y[a]-y[b]); c1=x[a]*x[a]+y[a]*y[a]-x[b]*x[b]-y[b]*y[b]; x2=2*x[b]-x[c]; y2=2*y[b]-y[c]; a2=2*(x2-x[b]); b2=2*(y2-y[b]); c2=x2*x2+y2*y2-x[b]*x[b]-y[b]*y[b]; if (fabs(a1)<eps) swap(a1,a2),swap(b1,b2),swap(c1,c2); if (fabs(a1)<eps) return false; if (fabs(a2)<eps) { y1=c2/b2; x1=(c1-b1*y1)/a1; x2=2*x[b]-x1; y2=2*y[b]-y1; } else { if (fabs(b1/a1-b2/a2)<eps && fabs(c1/a1-c2/a2)<eps) return false; y1=(c1-c2*a1/a2)/(b1-b2*a1/a2); x1=(c1-b1*y1)/a1; x2=2*x[b]-x1; y2=2*y[b]-y1; } double x4=2*x[a]-x1,y4=2*y[a]-y1; double x3=2*x[c]-x2,y3=2*y[c]-y2; if (meet(x[a],y[a],x4,y4,x[c],y[c],x3,y3)) return false; if ( fabs((x1-x2)*(y3-y2)-(x3-x2)*(y1-y2))<eps || fabs((x2-x3)*(y4-y3)-(x4-x3)*(y2-y3))<eps || fabs((x3-x4)*(y1-y4)-(x1-x4)*(y3-y4))<eps || fabs((x2-x1)*(y4-y1)-(x4-x1)*(y2-y1))<eps ) return false; if (meet(x1,y1,x2,y2,x3,y3,x4,y4)) return false; if (meet(x2,y2,x3,y3,x1,y1,x4,y4)) return false; if ( cross(x1,y1,x2,y2,x3,y3)*cross(x2,y2,x3,y3,x4,y4)<eps || cross(x2,y2,x3,y3,x4,y4)*cross(x3,y3,x4,y4,x1,y1)<eps || cross(x3,y3,x4,y4,x1,y1)*cross(x4,y4,x1,y1,x2,y2)<eps || cross(x4,y4,x1,y1,x2,y2)*cross(x1,y1,x2,y2,x3,y3)<eps ) return false; cout << "YES" << endl; printf("%.9f %.9f %.9f %.9f %.9f %.9f %.9f %.9f\n",x1,y1,x2,y2,x3,y3,x4,y4); return true; } int main() { cin >> t; while (t--) { for (i=1;i<=3;i++) cin >> x[i] >> y[i]; if ((x[1]==x[2] && y[1]==y[2])||(x[1]==x[3] && y[1]==y[3])||(x[2]==x[3] && y[2]==y[3])) {cout << "NO" <<endl << endl;continue;} if (solve(1,2,3)) continue; if (solve(2,1,3)) continue; if (solve(2,3,1)) continue; cout << "NO" << endl << endl; } return 0; }