UVA 11178 Morley’s Theorem(二维计算几何基础)

UVA 11178 Morley’s Theorem(二维计算几何基础)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=23&page=show_problem&problem=2119

题意:

给你一个三角形的A,B,C三点(逆时针给出),然后作该三角形的每个内角的三等分线, 相交成三角形DEF, 则DEF为等边三角形,要你输出DEF的坐标.

分析:

刘汝佳<<训练指南>>P259例题.

首先我们可以得到向量BC,然后我们根据向量BA可以算出角ABC的大小r,然后我们将向量BC逆时针旋转r/3弧度,就可以得到向量BD了.

同理我们将向量CB顺时钟旋转1/3的角ACB弧度可以得到向量CD向量,我们利用向量BD和CD求直线交点即可求出D坐标.

对于输入A,B,C我们可以这样求出D. 然后我们只要变换输入顺序为B ,C, A,我们可以求出E点坐标. 输入为C,A,B时,我们可以求出F点坐标.

AC代码:65行之前的代码都是刘汝佳的模板

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};

typedef Point Vector;

Vector operator+(Vector A,Vector B)
{
    return Vector(A.x+B.x, A.y+B.y);
}

Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x, A.y-B.y);
}

Vector operator*(Vector A,double p)
{
    return Vector(A.x*p, A.y*p);
}
Vector operator/(Vector A,double p)
{
    return Vector(A.x/p, A.y/p);
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Length(Vector A)
{
    return sqrt(Dot(A,A));
}
double Angle(Vector A,Vector B)
{
    return acos(Dot(A,B)/Length(A)/Length(B));
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
Vector Rotate(Vector A,double rad)
{
    return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad) );
}
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)
{
    Vector u =P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}

Point get_D(Point A,Point B,Point C)
{
    Vector v1=C-B,v2=A-B;
    double rad= Angle(v1,v2)/3;
    Vector v3=Rotate(v1,rad);

    Vector v4=B-C,v5=A-C;
    rad=Angle(v4,v5)/3;
    Vector v6=Rotate(v4,-rad);
    return GetLineIntersection(B,v3,C,v6);
}

int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        Point A,B,C;
        scanf("%lf%lf%lf%lf%lf%lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y);
        Point D=get_D(A,B,C);
        Point E=get_D(B,C,A);
        Point F=get_D(C,A,B);
        printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n",D.x,D.y,E.x,E.y,F.x,F.y);
    }
    return 0;
}