1572.Dandan's lunch

Time Limit: 1s Memory Limit: 256MB

As everyone knows, there are now $n$ people participating in the competition. It was finally lunch time after $3$ hours of the competition. Everyone brought a triangular bread. When they were going to eat bread, some people found that they solved more problems than others, but their bread was smaller than others. They thought it was very unfair. In this case, they will forcibly exchange bread with the other party (may be exchanged many times, someone can still exchange with others after being exchanged if the above conditions are satisfied, the other party can not refuse).

The description of the bread is given by the coordinates of the three vertices of the triangle. The size of the bread is twice the size of the triangle area, ensuring that there are no two breads of the same size, and the number of problems each person makes is different.

Dandan is also one of the contestants. Now he knows the number of problems solved by each person and the description of the bread they bring. Now he wants to know that after all the exchanges are over (That is, there can be no more exchanges between any two people), The size of the bread he can get.

Input Format(From the terminal/stdin)

The first line gives an integer $n$, which indicates the number of people who participated in the competition.

Lines $2 \sim n+1$, each line gives $7$ integers separated by spaces such as:
$num\ x_1\ y_1\ x_2\ y_2\ x_3\ y_3$
$num$ represents the number of the $i$th personal problem solving. $(x_1, y_1) (x_2, y_2) (x_3, y_3)$ represents the coordinates of the three points of the bread of the triangle with the $i$-th person. ensure that three points are not in the same line.

Notice that the second line (the first person) represents Dandan's information.

Data guarantee: $0 \lt n \le 1e^5,0 \le num \lt 1e^9, -1e^8 \lt x_1, x_2, x_3, y_1, y_2, y_3 \lt 1e^8$.

Output Format(To the terminal/stdout)

Outputs an integer representing the size of the bread that DanDan eventually gets.

Sample Input 1

Copy
1
100000000 0 0 10000 0 0 1000
 \n
         · · ·     · · ·    \n

Sample Output 1

Copy
10000000
        \n

Sample Input 2

Copy
4
3 0 0 1 0 0 1
1 0 0 2 0 0 2
2 0 0 3 0 0 3
4 0 0 4 0 0 4
 \n
 · · · · · · \n
 · · · · · · \n
 · · · · · · \n
 · · · · · · \n

Sample Output 2

Copy
9
 \n

Hints

For the first case: there's only Dandan alone.
For the second case: Dandan solved three problems, ranking second. Ranking first can get the biggest bread, so he can get the second largest bread.

Source: 2018 HNU新生赛

Submit

请先 登录

© 2025 FAQs