UVA - 11178 Morley's Theorem //几何初探

短命女 2022-08-12 13:29 114阅读 0赞

[Morley's Theorem][Morley_s Theorem]

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;3000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;Unknown</td> 
   <td>&nbsp;</td> 
   <td><strong>64bit IO Format:</strong>&nbsp;%lld &amp; %llu</td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][]\] \[Go Back\] \[[Status][]\]

**Morley’s Theorem  
Input:** Standard Input

**Output:** Standard Output

Morley’s theorem states that that the lines trisecting the angles of an arbitrary plane triangle meet at the vertices of an equilateral triangle. For example in the figure below the tri-sectors of angles A, B and C has intersected and created an equilateral triangle DEF.

![p11178.jpg][]

Of course the theorem has various generalizations, in particular if all of the tri-sectors are intersected one obtains four other equilateral triangles. But in the original theorem only tri-sectors nearest to BC are allowed to intersect to get point D, tri-sectors nearest to CA are allowed to intersect point E and tri-sectors nearest to AB are intersected to get point F. Trisector like BD and CE are not allowed to intersect. So ultimately we get only one equilateral triangle DEF. Now your task is to find the Cartesian coordinates of D, E and F given the coordinates of A, B, and C.

##### Input #####

First line of the input file contains an integer N (0<N<5001) which denotes the number of test cases to follow. Each of the next lines contain six integers ![p11178a.gif][]. This six integers actually indicates that the Cartesian coordinates of point A, B and C are ![p11178b.gif][] respectively. You can assume that the area of triangle ABC is not equal to zero, ![p11178c.gif][] and the points A, B and C are in counter clockwise order.

####  ####

#### Output ####

#### For each line of input you should produce one line of output. This line contains six floating point numbers ![p11178d.gif][] separated by a single space. These six floating-point actually means that the Cartesian coordinates of D, E and F are ![p11178e.gif][] respectively. Errors less than ![p11178f.gif][] will be accepted. ####

# Sample Input Output for Sample Input #

--------------------

**Problemsetters: Shahriar Manzoor**

**Special Thanks: Joachim Wulff**

Source

Root :: Prominent Problemsetters :: [Shahriar Manzoor][]  
  
Root :: AOAPC I: Beginning Algorithm Contests -- Training Guide (Rujia Liu) :: Chapter 4. Geometry :: Geometric Computations in 2D :: [Examples][]

#include <stdio.h>
    #include <math.h>
    
    #define PI 57.29577957855229 // 180/3.14159265
    #define No 999999.9
    #define MIN 1e-8
    
    struct Point
    {
        double x;
        double y;
    };
    struct Line
    {
        double k;
        double b;
    };
    
    Point get_point(struct Line AB, double a, struct Line BC, double b,Point A, Point B);
    Line get_line(struct Point a, struct Point b);
    double get_agree(struct Point a, struct Point b, struct Point c);
    
    int main()
    {
        Point A, B, C;
        Line AB, BC, CA;
        Point p1, p2, p3;
    
        double a, b, c;
        int t;
    
        scanf("%d", &t);
        while(t--)
        {
            scanf("%lf%lf%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);
    
            a = get_agree(B, A, C);
            b = get_agree(A, B, C);
            c = get_agree(B, C, A);
    
            AB = get_line(A, B);
            BC = get_line(B, C);
            CA = get_line(A, C);
    
            p1 = get_point(BC, b, CA, c, B, C);
            p2 = get_point(CA, c, AB, a, C, A);
            p3 = get_point(AB, a, BC, b, A, B);
    
            printf("%.6f %.6f %.6f %.6f %.6f %.6f\n", p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
        }
        return 0;
    }
    Point get_point(struct Line AB, double a, struct Line BC, double b, Point A, Point B)
    {
        Point p;
    
        if(fabs(AB.k - No) > MIN)
        {
    
            AB.k = tan( (atan(AB.k)*PI + a/3.0)/PI );
        }
        else
        {
            AB.k = tan((90.0 + a/3.0)/PI);
        }
    
        if(fabs(BC.k - No) > MIN)
        {
            BC.k = tan( (atan(BC.k)*PI + (b/3.0)*2.0)/PI );
        }
        else
        {
            BC.k = tan((90.0 + (b/3.0)*2.0)/PI);
        }
        AB.b = A.y - AB.k*1.0*A.x;
        BC.b = B.y - BC.k*1.0*B.x;
    
        p.x = (BC.b - AB.b)/((AB.k - BC.k)*1.0);
        p.y = AB.k * p.x*1.0 + AB.b;
    
        return p;
    }
    Line get_line(struct Point a, struct Point b)
    {
        Line l;
    
        if(fabs(b.x-a.x) > MIN)
        {
            if(fabs(b.y-a.y) < MIN)
               l.k = 0.0;
            else
                l.k = (b.y - a.y)/((b.x - a.x)*1.0);
            l.b = a.y - l.k * a.x*1.0;
        }
        else
        {
            l.k = No;
            l.b = a.y;
        }
        return l;
    }
    double get_agree(struct Point a, struct Point b, struct Point c)
    {
        Point ab, bc;
        double A;
    
        ab.x = a.x - b.x;
        ab.y = a.y - b.y;
    
        bc.x = c.x - b.x;
        bc.y = c.y - b.y;
    
        A = (ab.x*bc.x + ab.y*bc.y)/(( sqrt(ab.x*ab.x + ab.y*ab.y)*sqrt(bc.x*bc.x + bc.y*bc.y) )*1.0);
    
        return acos(A)*PI;
    
    }

[Morley_s Theorem]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2119
[Submit]: http://vjudge.net/vjudge/problem/toSubmit.action?id=18543
[Status]: http://vjudge.net/vjudge/problem/status.action?id=18543
[p11178.jpg]: /images/20220810/fb6c9ef353764ce8ae4eb1a661451cc9.png
[p11178a.gif]: http://uva.onlinejudge.org/external/111/p11178a.gif
[p11178b.gif]: http://uva.onlinejudge.org/external/111/p11178b.gif
[p11178c.gif]: /images/20220810/76deb886e6b94b53b20807b5e5fcbfaa.png
[p11178d.gif]: http://uva.onlinejudge.org/external/111/p11178d.gif
[p11178e.gif]: http://uva.onlinejudge.org/external/111/p11178e.gif
[p11178f.gif]: /images/20220810/1c633004a7224388b3039824779194f7.png
[Shahriar Manzoor]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=44
[Examples]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=528