Kyuhyun and Seunghwan's Twin Birthday Cake
Time limit1sMemory limit128 MB
Given a triangle's vertices, compute a line (in normalized Ax+By=C form) that splits the triangle into two regions of equal area and equal perimeter simultaneously.
- Level
Hard8 of 10
- Topics
- Geometry, Binary search, Math
- Solved
- No attempts yet
Problem
Donggyu buys a triangular birthday cake every year for his twin sons Seunghwan and Kyuhyun. The shape of the cake changes each year. The sides of the cake are covered with chocolate icing, and the top is covered with pink icing. Since both children like both kinds of icing, they want to receive equal amounts.
Write a program that finds a way to cut the cake so that Kyuhyun and Seunghwan receive equal amounts.
A triangle equalizer is a line segment that divides a triangle into two parts with the same perimeter and the same area. The segment passes through the triangle and connects two points on its boundary.
In general, a triangle has one, two, or three equalizers. The case with exactly two occurs only under a special condition.
Given a triangle, find any one equalizer for it. Double-precision floating-point calculations are sufficient.
Input
The first line contains the number of test cases P (1 <= P <= 1000). Each test case is given on one line and contains six real numbers: the coordinates of the triangle's vertices in the order x0 y0 x1 y1 x2 y2.
Every input real number has absolute value less than 20 and is given with exactly five digits after the decimal point.
Output
For each test case, output the equation of one equalizer line of the given triangle. Write the equation in the form Ax + By = C, and print A, B, and C separated by spaces with exactly five digits after the decimal point.
The coefficients must satisfy A*A + B*B = 1.0 and A >= 0.