Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.
ContestId |
Name |
Phase |
Frozen |
Duration (Seconds) |
Relative Time |
Start Time |
|---|---|---|---|---|---|---|
| 2041 | 2024 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) | FINISHED | False | 18000 | 44492085 | Nov. 24, 2024, 7:05 a.m. |
Solved |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
|---|---|---|---|---|---|---|
| ( 70 ) | L | Building Castle | PROGRAMMING |
A-Ju has a gorgeous castle in which she often enjoys living. However, she gets tired of living in the castle for a long time. Thus, she decides to rebuild her castle into some specific shape to make her it more beautiful. Let's say we represent A-Ju's castle as a 2D convex polygon (^{\text{∗}}) on the 2D plane. A-Ju aims to rebuild her castle into a point symmetric convex polygon. Here, a polygon is point symmetric if there exists a center (c) such that for every point (p) in the polygon, the reflection (p^\prime) of (p) across (c) is also in the polygon. While designing an arbitrary point symmetric convex polygon shape is easy, the cost of rebuilding is very high. After some estimation, A-Ju found that the cost of rebuilding is proportional to the area of the symmetric difference(^{\text{†}}) between the original castle and the new castle. See the following figure for an example: In the example above, A-Ju's castle is a shape of the convex polygon formed by points ((3, 7) - (2, 1) - (6, 3)). After rebuilding her castle into the shape of the polygon formed by ((3, 7) - (\frac{7}{3}, 3) - (\frac{13}{3}, \frac{1}{3}) - (5, \frac{13}{3})), the area of the symmetric difference between these two polygons will be (\frac{11}{3}). The difference can be calculated as the sum of the additional area (represented by the green grid region) and the shaved area (represented by the red line region). Please write a program that helps A-Ju design a blueprint of the new castle, such that the area of the symmetric difference between the original one and the new one is minimized. You only need to output the minimum value since A-Ju wants to estimate her cost first. (^{\text{∗}})A polygon (P) is convex if for every two points (p, q \in P), the line segment connecting them is also contained in (P), i.e., (tp + (1-t)q \in P) for all (t \in 0, 1). Equivalently, it is a polygon whose interior angles are all less than |
| Problem Analysis and Hints (PDF) |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 293160667 | rainbowbunny | L | Nov. 25, 2024, 12:44 a.m. | OK | C++20 (GCC 13-64) | TESTS | 27 | 655 | 102400 | ||
| 293056027 | JoeyJ liyelin KevinLikesCoding | L | Nov. 24, 2024, 8:59 a.m. | OK | C++20 (GCC 13-64) | TESTS | 27 | 1327 | 204800 | ||
| 293087186 | cxm1024 IceYukino pp_orange | L | Nov. 24, 2024, 11:47 a.m. | OK | C++20 (GCC 13-64) | TESTS | 27 | 2952 | 36966400 | ||
| 293091834 | BernatP | L | Nov. 24, 2024, 12:19 p.m. | OK | C++20 (GCC 13-64) | TESTS | 27 | 4609 | 102400 | ||
| 293090334 | BernatP | L | Nov. 24, 2024, 12:08 p.m. | OK | C++20 (GCC 13-64) | TESTS | 27 | 8530 | 102400 | ||
| 293171378 | Ion_Gravirei | L | Nov. 25, 2024, 4:45 a.m. | OK | C++23 (GCC 14-64, msys2) | TESTS | 27 | 2827 | 36966400 | ||
| 293018916 | L | Nov. 24, 2024, 1:17 a.m. | OK | Unknown | TESTS | 0 | 0 | 0 | |||
| 293018874 | L | Nov. 24, 2024, 1:17 a.m. | OK | Unknown | TESTS | 0 | 0 | 0 |
Back to search problems