| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3741 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3489 |
| 7 | Radewoosh | 3483 |
| 8 | Kevin114514 | 3443 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 158 |
| 5 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | djm03178 | 155 |
| 9 | TheScrasse | 154 |
| 10 | Dominater069 | 153 |
"In a triangulation of a regular n-gon, there always exists a diagonal that divides the polygon into 2 small polygons and the smaller one has at least 
vertices."
I saw this property in the NEERC 2014's editorial but still cannot prove it. Can anyone help me? Thank you!
Auto comment: topic has been updated by cuom1999 (previous revision, new revision, compare).
Take a dual tree to the triangulation (introduce a vertex inside every triangle and put an edge if faces share a diagonal) and find a centroid of this tree and diagonal you are looking for is one corresponding to the edge from centroid to its son with the biggest size of its subtree.
I think you mean NEERC 2015, not 2014.
Consider the triangle XYZ containing the circumcenter of the polygon. Without loss of generality let XY be the longest minor arc among XY, YZ and ZX. Then XY is the diagonal you're looking for, as it has at least n / 3 vertices on one side and at least n / 2 vertices on the other.