Greedy Students GRDSTD SOLUTION Code Chef
Rafid is teaching his students plane geometry. Today they are talking about convex polygons. A convex polygon is a simple non-degenerate polygon such that each of its internal angles is strictly smaller than 180∘180∘.
Rafid drew NN points (numbered 11 through NN) on a blackboard (a two-dimensional plane) and told each student to choose some of the points and connect them to obtain a convex polygon. For each valid ii, the coordinates of the ii-th point are (Xi,Yi)(Xi,Yi).
There are KK students (numbered 11 through KK). To prevent the students from choosing the same polygon over and over, Rafid told them that they have to choose polygons one by one in the order from student 11 to student KK and each student has to choose a set of points which was not chosen by any earlier student. That means they have to choose KK different sets of points, resulting in KK different polygons. As a result, some students may end up unable to choose any polygon.
To encourage the students, Rafid announced that each student will receive a number of candies proportional to the area of this student’s polygon. The students are very greedy, so the first student will choose the polygon with the largest area, the second student will choose the polygon with the largest area which does not use the same set of points as the first student’s polygon, and so on.
For each student, help Rafid find the area of the polygon chosen by this student or determine that this student cannot choose a polygon anymore. Note that while there may be many ways in which the students could choose their polygons, their areas are uniquely determined.
- The first line of the input contains two space-separated integers NN and KK.
- NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers XiXi and YiYi.
Print a single line containing KK space-separated integers A1,A2,…,AKA1,A2,…,AK. For each valid ii, AiAi should be twice the area of a polygon chosen by the ii-th student, or −1−1 if all possible polygons have already been chosen by students before the ii-th student.
- |Xi|,|Yi|≤106|Xi|,|Yi|≤106 for each valid ii
- the points (X1,Y1),(X2,Y2),…,(XN,YN)(X1,Y1),(X2,Y2),…,(XN,YN) are pairwise distinct
Subtask #1 (5 points):
- it is possible to form at least KK convex polygons
Subtask #2 (15 points): K≤1,000K≤1,000
Subtask #3 (80 points): original constraints
5 15 0 0 10 0 10 10 0 10 5 5
200 100 100 100 100 50 50 50 50 -1 -1 -1 -1 -1 -1
The following figure describes the points and some polygons.
- The first student chooses the largest polygon ABCDABCD with area 100100.
- The next four students choose the triangles ABCABC, BCDBCD, CDACDA and DABDAB, each with area 5050. Note that for example, the polygon AECBAECB is not convex because it has one internal angle equal to 180∘180∘.
- The next four students choose the triangles AEBAEB, BECBEC, CEDCED and DEADEA, each with area 2525.
- There are no more polygons the students can choose, so the remaining six students are left without a polygon.
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef