1726 . Pizza Equalization
TopCoder
Description
The PDF version of this problem can be downloaded here.
Have you heard the story of killing three warriors with two peaches? Now you have two pizzas and would like to give to three friends of yours. Of course, you do not want them
to ght for the pizza, so you must divide the pizzas into three equal-sized portions.
Both pizzas you have are in convex quadrilateral shape, and they have one side in common. As shown in the gure below, ABCD and CDFE are your pizzas. You are also given two lines, L1 and L2. You have to choose a point on each line (like P on L1 and Q on L2), so that the area of region ABP, CPDQ, and QFE are exactly the same. Moreover, P should lie in ABCD and Q should lie in CDFE. Then, you may give each friend one of the three pieces.
How about other pieces, such as ACP and CQE? Those are for yourself!
Input Format
The first line of the input le contains an integer T (1 ≤ T ≤ 100) indicating the number of test cases.
Each test case consists of three lines. The rst line contains 12 integers, Ax, Ay, Bx,
By, Cx, Cy, Dx, Dy, Ex, Ey, Fx, and Fy, denoting the x and y coordinates of points A to F. The second line contains 4 integers, L11,x, L11,y, L12,x, and L12,y, denoting two points on L1. The third line also contains 4 integers, L21,x, L21,y, L22,x, and L22,y,
denoting two points on L2. All the coordinates are in the range [0; 514].
Output Format
For each test case output 4 numbers, Px, Py, Qx, and Qy, denoting the two chosen points. If there are multiple solutions, output the one with smallest Px. If there are
still multiple solutions, output the one with smallest Py, and then Qx, and then Qy. Otherwise, if there are no solution, output "No solution"(without quote) in one line. A solution with absolute error at most 10-6 will be accepted.
Sample Input 1
1 0 10 0 0 5 10 5 0 10 10 10 0 0 0 5 10 5 0 10 10
Sample Output 1
3.3333333 6.6666667 6.6666667 3.3333333
Hints
Info: 本題輸出為浮點數，絕對或相對誤差 1e-6 以下視為正確
Problem Source
Migrated from old NTUJ.
dreamoon
Subtasks
| No. | Testdata Range | Score |
|---|