UVA - 11178 Morley's Theorem

按照刘汝佳老师说的,这道题本身没有什么算法可言,

主要是考察选手对于几何算法的应用,

我们已经知道了点A,B,C

如果要求点D的话

我们可以先求出向量C-B的坐标,然后求出向量C-B与A-B的夹角。

再把夹角/3,这样我们就找到了∠CBD的度数。

再把向量C-B逆时针旋转∠CBD度

就求出了点D的坐标,

E,F同理

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<cmath>
  5 #define Vector Point
  6 using namespace std;
  7 inline void read(int &n)
  8 {
  9     char c='+';bool flag=0;n=0;
 10     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 11     while(c>='0'&&c<='9')    n=n*10+(c-48),c=getchar();
 12     if(flag==1)n=-n;
 13 }
 14 const double PI=acos(-1);
 15 const double eps=1e-10;
 16 int dcmp(double x)    {return (fabs(x)<eps)?0:(x<0?-1:1);}
 17 struct Point
 18 {
 19     double x,y;
 20     Point(double x=0,double y=0):x(x),y(y){};
 21 };
 22 Vector operator + (Vector A,Vector B) {return Vector(A.x + B.x,A.y + B.y);}
 23 Vector operator - (Vector A,Vector B) {return Vector(A.x - B.x,A.y - B.y);}
 24 Vector operator * (Vector A,double P) {return Vector(A.x * P,A.y * P);}
 25 Vector operator / (Vector A,double P) {return Vector(A.x / P,A.y / P);}
 26 bool operator < (const Point &a,const Point &b){return a.x < b.x || (a.x == b.x && a.y < b.y);}
 27 bool operator == (const Point &a,const Point &b){return dcmp(a.x - b.x)==0 && dcmp(a.y - b.y)==0;}
 28 
 29 double Dot(Vector A,Vector B){return A.x * B.x + A.y * B.y;}//点积 ********************
 30 double Length(Vector A){return sqrt(Dot(A,A));}// 求向量的长度 
 31 double Angle(Vector A,Vector B){return acos(Dot(A,B) / (Length(A)) / Length(B));} //求两个向量的夹角 
 32 
 33 double Cross(Vector A,Vector B){return A.x * B.y-A.y * B.x;}// 两个向量的叉积 
 34 double Area2(Point A,Point B,Point C){return Cross(B - A,C - A);}
 35 
 36 Vector Rotate(Vector A,double rad){return Vector(A.x * cos(rad)-A.y * sin(rad),A.x * sin(rad)+A.y * cos(rad));}// 向量旋转********* 
 37 
 38 Point GetLineIntersection(Point P,Point v,Point Q,Point w)// 两直线的交点 ****************
 39 {
 40     Vector u=P-Q;
 41     double t=Cross(w,u)/Cross(v,w);
 42     return P+v*t;
 43 }
 44 
 45 double DistanceToLine(Point P,Point A,Point B)// 点P到直线AB的距离 
 46 {
 47     Vector v1=B - A;Vector v2= P-A;
 48     return fabs(Cross(v1,v2)) / Length(v1);
 49 }
 50 
 51 double DistanceToSegment(Point P,Point A,Point B)// 点P到线段AB的距离 
 52 {
 53     if(A==B)    return Length(P-A);
 54     Vector v1=B-A, v2=P-A, v3=P-B;
 55     if(dcmp(Dot(v1,v2)) < 0)    return Length(v2);
 56     else if(dcmp(Dot(v1,v3)) > 0)    return Length(v3);// 怎么会是大于。。。。。。
 57     else return fabs(Cross(v1,v2)) / Length(v1);        
 58 }
 59 
 60 Point GetLineProjection(Point P, Point A, Point B)// 求点P在直线AB上的正投影 
 61 {
 62     Vector v=B-A;
 63     return A+v*(Dot(v, P-A) / Dot(v,v));
 64 }
 65 
 66 bool SegmentProperIntersection(Point a1, Point a2, Point b1,Point b2)//判断两直线是否相交 
 67 {
 68     double c1 = Cross(a2-a1,b1-a1) , c2 = Cross(a2-a1,b2-a1),
 69            c3 = Cross(b2-b1,a1-b1) , c4 = Cross(b2-b1,a2-b1);
 70     return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
 71 }
 72 
 73 double PolygonArae(Point *p,int n)// 求多边形的有向面积 
 74 {
 75     double area = 0;
 76     for(int i=1;i<=n-1;i++)
 77         area += Cross(p[i]-p[0],p[i+1]-p[0]);
 78     return area/2;
 79 }
 80 Point read_point()
 81 {
 82     double x,y;
 83     scanf("%lf%lf",&x,&y);
 84     return Point(x,y);
 85 }
 86 Point getans(Point A,Point B,Point C)
 87 {
 88     Vector v1= C-B;
 89     double ang1=Angle(A-B,v1);
 90     v1=Rotate(v1,ang1/3);
 91     
 92     Vector v2= B-C;
 93     double ang2=Angle(A-C,v2);
 94     v2=Rotate(v2,-ang2/3);
 95     
 96     return GetLineIntersection(B,v1,C,v2);
 97 }
 98 int main()
 99 {
100     int T;read(T);
101     while(T--)
102     {
103         Point A,B,C,D,E,F;
104         A=read_point();
105         B=read_point();
106         C=read_point();
107         D=getans(A,B,C);
108         E=getans(B,C,A);
109         F=getans(C,A,B);
110         printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n", D.x, D.y, E.x, E.y, F.x, F.y);
111     }
112     
113     return 0;
114 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LeetCode 149. Max Points on a Line分析代码

将x,y的差值求最大公约数,约到最简洁的形式,然后存入map中,对每个点这样操作,如果最后x,y最后相等,那么就说明两个点具有相同的斜率,在一条直线上。同时不要...

953
来自专栏CDA数据分析师

入门 | 数据科学初学者必知的NumPy基础知识

NumPy(Numerical Python)是 Python 中的一个线性代数库。对每一个数据科学或机器学习 Python 包而言,这都是一个非常重要的库,S...

1342
来自专栏杂七杂八

numpy.nonzero()函数

官方文档如下: numpy.nonzero(a) Return the indices of the elements that are non-zero....

2363
来自专栏程序生活

Tensorflow教程(十三) tf.Variable() 和tf.get_variable()1 简介2 区别3 实例

2043
来自专栏Java帮帮-微信公众号-技术文章全总结

Java案例-分数查等级程序

Java案例-分数查等级程序 给定一个百分制的分数,输出相应的等级。 90分以上 A级 80~89 B级 70~79 C级 ...

3958
来自专栏mathor

搜索(6)

 题目大意是在一个nxn的方阵地图上,每一个方格都标记+号或者-号,要从A点到B点。题目要求移动路线要+-交替,问怎么移动从A到B才是最短路径?  同样...

1373
来自专栏ACM算法日常

POJ1258:Agri-Net-最小生成树

Farmer John has been elected mayor of his town! One of his campaign promises was...

962
来自专栏GopherCoder

xpath 和 pyquery

3003
来自专栏架构之路

并查集Union-find及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。 本文首先介绍并查集的定义、原理及...

3474
来自专栏人工智能

如何为机器学习索引,切片,调整 NumPy 数组

具体在 Python 中,数据几乎被都被表示为 NumPy 数组。

6867

扫码关注云+社区

领取腾讯云代金券