首页 > 代码库 > CodeForces 23D Tetragon 给定凸四边形3条同边长的中点求4个顶点 计算几何
CodeForces 23D Tetragon 给定凸四边形3条同边长的中点求4个顶点 计算几何
题目链接:点击打开链接
题意:
给定3个二维平面上的点
这3个点是一个凸四边形的其中3个中点
问是否存在这样的四边形,若存在则输出四边形顶点
思路:
那个外面的点是一个中点关于另一个中点对称得到的
然后得到一个圆的2条弦,圆心就是4个顶点之一,剩下对称出来即可
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> #include <set> #include <stdlib.h> using namespace std; #define ST 1001 #define EN 1002 #define M 10000 #define inf 1000000 #define eps 1e-8 #define PR 1e-8 #define node Point struct Point{//点是2维的 double x,y; }p[50],aa[3],ans[4]; double Cross(Point p1,Point p2,Point p3,Point p4){//二维向量(p1p2)X(p3p4) 返回第三向量长度 double x1=p2.x-p1.x,y1=p2.y-p1.y; double x2=p4.x-p3.x,y2=p4.y-p3.y; return x1*y2-x2*y1; //为0表示 p1p2 与p3p4共线 //直线:不为0就是相交 } bool On_Segment(Point p1,Point p2,Point p3){//p3点在 p1p2线段上 if(Cross(p1,p2,p1,p3)!=0)return false; bool iny=(p1.y<=p3.y && p3.y<=p2.y)||(p1.y>=p3.y && p3.y>=p2.y); bool inx=(p1.x<=p3.x && p3.x<=p2.x)||(p1.x>=p3.x && p3.x>=p2.x); if(inx && iny)return true; return false; } bool Segmentintersect(Point p1,Point p2,Point p3,Point p4){//p1p2 是否与 p3p4相交 double cross_1=Cross(p3,p4,p3,p1),cross_2=Cross(p3,p4,p3,p2);//cross_1 2必须一正一负且都不为0 double cross_3=Cross(p1,p2,p1,p3),cross_4=Cross(p1,p2,p1,p4);//cross_2 4必须一正一负且都不为0 //表示a线段 2点 在b线段 2侧 if(cross_1*cross_2<0 && cross_3*cross_4<0)return true; //a线段端点在 b线段上 视情况取舍这种位置 // if(cross_1==0 && On_Segment(p3,p4,p1))return true; // if(cross_2==0 && On_Segment(p3,p4,p2))return true; // if(cross_3==0 && On_Segment(p1,p2,p3))return true; // if(cross_4==0 && On_Segment(p1,p2,p4))return true; return false; } #define N 105 #define eps 1e-8 double Abs(double x){return x>0?x:-x;} bool equal(double a,double b){return Abs(a-b)<eps;} node dui(node xx, node yy){ node now ; now.x = 2*yy.x-xx.x; now.y = 2*yy.y-xx.y; return now; } double dis(node xx,node yy){ return sqrt((xx.x-yy.x)*(xx.x-yy.x)+(xx.y-yy.y)*(xx.y-yy.y)); } node hehe(node a,node b,node c){ node now; double a1=b.x-a.x, b1=b.y-a.y, c1=(a1*a1+b1*b1)/2; double a2=c.x-a.x, b2=c.y-a.y, c2=(a2*a2+b2*b2)/2; double d =a1*b2-a2*b1; now.x = a.x+(c1*b2-c2*b1)/d; now.y = a.y+(a1*c2-a2*c1)/d; return now; } bool gongxian(node a,node b,node c){ if(!(equal((b.x+c.x)/2.0,a.x)&&equal((b.y+c.y)/2.0,a.y))) swap(a,b); if(!(equal((b.x+c.x)/2.0,a.x)&&equal((b.y+c.y)/2.0,a.y))) return false; return equal(dis(a,b),dis(a,c)); } bool work(node a,node b,node c){ if(gongxian(a,b,c))return false; node bb = dui(b,a); if(gongxian(a,bb,c))return false; ans[1] = hehe(a,bb,c); ans[2] = dui(ans[1],a); ans[3] = dui(ans[2],b); ans[0] = dui(ans[1],c); return Segmentintersect(ans[1],ans[3],ans[0],ans[2]); } int main(){ int T;scanf("%d",&T); while(T--){ for(int i = 0; i < 3; i++)scanf("%lf %lf",&aa[i].x,&aa[i].y); if(work(aa[0],aa[1],aa[2])||work(aa[1],aa[0],aa[2])||work(aa[2],aa[1],aa[0])){ puts("YES"); for(int i = 0; i < 4; i++){ printf("%.10lf %.10lf",ans[i].x,ans[i].y); if(i==3)puts(""); else printf(" "); } } else puts("NO"), puts(""); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。