Problem A

Triangle Fun 

Input: Standard Input

Output: Standard Output

 

In the picture below you can see a triangle ABC. Point D, E and F divides the sides BC, CA and AB into ratio 1:2 respectively. That is CD=2BD, AE=2CE and BF=2AF. A, D; B, E and C, F are connected. AD and BE intersects at P, BE and CF intersects at Q and CF and AD intersects at R.

 

So now a new triangle PQR is formed. Given triangle ABC your job is to find the area of triangle PQR.

 

Input

First line of the input file contains an integer N (0<N<1001) which denotes how many sets of inputs are there. Input for each set contains six floating-point number A_x, A_y, B_x, B_y, C_x, C_y. (0≤A_x, A_y, B_x, B_y, C_x,C_y ≤10000) in one line line. These six numbers denote that the coordinate of points A, B and C are (A_x, A_y), (B_x, B_y) and (C_x, C_y) respectively. A, B and C will never be collinear.

 

Output

For each set of input produce one line of output. This one line contains an integer AREA. Here AREA is the area of triangle PQR, rounded to the nearest integer.

 

Sample Input

2

3994.707 9251.677 4152.916 7157.810 5156.835 2551.972

6903.233 3540.932 5171.382 3708.015 213.959 2519.852

 

Output for Sample Input

98099

206144

 

---

Problemsetter: Shahriar Manzoor

---

 

　　计算几何，求直线交点，向量运算，求三角形面积。

　　这道题是计算几何基本知识的混合应用，用到了以上知识，但是都不难。思路是先用 “点 + 向量 = 点” 的原理，求出每一个边的三分点。然后求每一对三分线的交点即为所求三角形的三个顶点。最后求出三角形面积即可。

　　需要注意的是，最后输出的时候要求是四舍五入（“rounded to”是四舍五入的意思）是取整数，所以要 +0.5 再强制转换为int（强制转换是直接砍掉小数点后的部位）。因为这个原因WA了两次，改正后才AC，唉，万恶的英语。

　　代码：

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 #define eps 1e-10 5 /********** 定义点 **********/ 6 struct Point{ 7     double x,y; 8     Point(double x=0,double y=0):x(x),y(y) {} 9 };10 /********** 定义向量 **********/11 typedef Point Vector;12 /********** 向量 + 向量 = 向量 **********/13 Vector operator + (Vector a,Vector b)14 {15     return Vector(a.x+b.x,a.y+b.y);16 }17 /********** 点 - 点 = 向量 **********/18 Vector operator - (Point a,Point b)    19 {20     return Vector(a.x-b.x,a.y-b.y);21 }22 /********** 向量 * 数 = 向量 **********/23 Vector operator * (Vector a,double b)24 {25     return Vector(a.x*b,a.y*b);26 }27 /********** 向量 / 数 = 向量 **********/28 Vector operator / (Vector a,double b)29 {30     return Vector(a.x/b,a.y/b);31 }32 /********** 2向量求叉积 **********/33 double Cross(Vector a,Vector b)34 {35     return a.x*b.y-b.x*a.y;36 }37 /********** 3点求叉积 **********/38 double Cross(Point a,Point b,Point c)39 {40     return (c.x-a.x)*(b.y-a.y) - (c.y-a.y)*(b.x-a.x);41 }42 /********** 直线交点 **********/43 Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)44 {45     Vector u = P-Q;46     double t = Cross(w,u) / Cross(v,w);47     return P+v*t;48 }49 int main()50 {51     int n;52     cin>>n;53     while(n--){54         Point a,b,c;55         cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y;56         Point d,e,f;    //每边的三分点57         d = b + (c-b)/3;58         e = c + (a-c)/3;59         f = a + (b-a)/3;60         Point p,q,r;    //中间三角形的三顶点61         p = GetLineIntersection(a,d-a,b,e-b);62         q = GetLineIntersection(b,e-b,c,f-c);63         r = GetLineIntersection(a,d-a,c,f-c);64         cout<
      
     

 

Freecode :