UVA – 11178
Morley’s Theorem
Time Limit:3000MSMemory Limit:Unknown64bit IO Format:%lld & %llu
Submit
Description
Problem DMorley’s TheoremInput: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.
Of coursethe 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.Trisectorlike 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 sixintegers.Thissix integers actually indicates that the Cartesian coordinates of point A, B and C areand the points A, B and C are in counter clockwise order.
OutputFor each line of input you should produce one line of output. This line contains six floating point numbersseparated by a single space. These six floating-point actually means that the Cartesian coordinates of D, E and F arewill be accepted.
Sample InputOutput for Sample Input
2 1 1 2 2 1 2 0 0 100 0 50 50
1.316987 1.816987 1.183013 1.683013 1.366025 1.633975
56.698730 25.000000 43.301270 25.000000 50.000000 13.397460
Problemsetters: Shahriar Manzoor
Special Thanks: Joachim Wulff
Source
Root :: Prominent Problemsetters ::Shahriar ManzoorRoot :: AOAPC I: Beginning Algorithm Contests — Training Guide (Rujia Liu) :: Chapter 4. Geometry :: Geometric Computations in 2D ::Examples
思路：首先需要计算角ABC的值b，然后把射线BC逆时针旋转b/3，得到直线BD。同理可求得CD，，求交点D即可。。同理可以求得E，F。
AC代码：
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <cmath>using namespace std;struct Point {double x, y;Point(double x = 0, double y = 0) : x(x) , y(y) { } //构造函数，方便代码编写 };typedef Point Vector; //从程序实现上，Vector只是Point的别名 //向量 + 向量 = 向量 ，点 + 向量 = 点Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }//点 – 点 = 向量Vector operator – (Vector A, Vector 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); } bool operator < (const Point& a, const Point& b) {return a.x < b.x || (a.x == b.x && a.y < b.y);} const double eps = 1e-10;int dcmp(double x) {if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;}bool operator == (const Point& a, const Point& b) {return dcmp(a.x – b.x) == 0 && dcmp(a.y – b.y) == 0;}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; }//求叉积 double Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); }//根据叉积求三角形面积的两倍 Vector Rotate(Vector A, double rad) {//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_point(Point A, Point B, Point C) {Vector v1 = C – B;double a1 = Angle(A-B, v1);v1 = Rotate(v1, a1/3);Vector v2 = B – C;double a2 = Angle(A-C, v2);v2 = Rotate(v2, -a2/3); //负数表示顺时针旋转 return GetLineIntersection(B, v1, C, v2); }int main() {int T;Point A, B, C, D, E, F;scanf("%d", &T);while(T–) {scanf("%lf %lf %lf %lf %lf %lf", &A.x, &A.y, &B.x, &B.y, &C.x, &C.y);D = get_point(A, B, C);E = get_point(B, C, A);F = get_point(C, A, B);printf("%lf %lf %lf %lf %lf %lf\n", D.x, D.y, E.x, E.y, F.x, F.y);} return 0;}
都可以…孔子的,老子的. 孙子的…都可以
