Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

My first problem in 2023: "Genshin Geometry" !!!

Revision en50, by Yunannnn, 2023-01-02 16:45:11

Let your spirit soar and have a joy-filled new year by playing Ghenshin :D

However, before that, I will recommend to you an interesting "Genshin Geometry" problem

(Problem F from the GYM The 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)).

Summary: Give N distint points on the plane, and special point O = (0, 0). Your task is dividing this N points into two sets A and B so that:

  • Both of them is a strict convex set.

  • The outlines(edge) of two convex hulls only intersect at point O.

  • The sum of the perimeters of these two convex hulls is maximum.

So now, let's try to solve this problem by yourself...

.

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

                                                 .

...before reading some hints!

Firstly, let's answer this question: Is there any TRICKS to contruct these two sets optimally directly ?. (It becomes a Greedy problem!!!). In my opinion, this problem has a lot of cases, and the greedy solution is difficult to approach. So, I will representation a general solution, but if you have a more optimal solution, please leave your commend and everyone can reference.

Tags

This problem has two general case. The first case is easier to approach: convex hull covers convex hull.

Image

So, set A is the convex hull of N points , and there are M remaining points that do not lie on this convex hull. Obviously, these M points are belong to the set B. Note, we need to check if remaining M points is strict convex and don't forget to the point O.

But wait, is there any special cases?

The answer is

The second case is dividing line.

For example

The line connecting point O and any other point divides these N points into two groups. For more clearly, see this

Image

So, the solution is: For each point, divide N points with line connecting point O and that point into two groups, check if these groups are convex and find the maximum perimeters of all such dividing. But,

How to do it
My solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en61 English Yunannnn 2023-01-02 17:30:31 0 (published)
en60 English Yunannnn 2023-01-02 17:29:27 8 Tiny change: ' return — 1;\n }' -> ' return - 1;\n }'
en59 English Yunannnn 2023-01-02 17:28:04 64
en58 English Yunannnn 2023-01-02 17:22:47 5
en57 English Yunannnn 2023-01-02 17:20:54 452
en56 English Yunannnn 2023-01-02 17:11:12 21
en55 English Yunannnn 2023-01-02 17:10:04 440
en54 English Yunannnn 2023-01-02 16:58:51 106
en53 English Yunannnn 2023-01-02 16:55:07 249
en52 English Yunannnn 2023-01-02 16:47:19 54
en51 English Yunannnn 2023-01-02 16:46:19 3 Tiny change: ' **N** is 10^6.\n</spoil' -> ' **N** is $10^6$.\n</spoil'
en50 English Yunannnn 2023-01-02 16:45:11 320
en49 English Yunannnn 2023-01-02 16:38:11 53
en48 English Yunannnn 2023-01-02 16:34:18 197
en47 English Yunannnn 2023-01-02 16:27:25 40
en46 English Yunannnn 2023-01-02 16:25:15 7 Tiny change: '(https://imgur.com/vj1L69y)\n</spoil' -> '(https://i.imgur.com/vj1L69y.png)\n</spoil'
en45 English Yunannnn 2023-01-02 16:24:27 15 Tiny change: 'j1L69y)\n<spoiler' -> 'j1L69y)\n</spoiler>\n\n<spoiler'
en44 English Yunannnn 2023-01-02 16:23:32 151
en43 English Yunannnn 2023-01-02 16:18:04 1453
en42 English Yunannnn 2023-01-02 16:14:21 9703
en41 English Yunannnn 2023-01-02 16:12:02 3 Tiny change: 'so easy.\n![ ](htt' -> 'so easy.\n\n![ ](htt'
en40 English Yunannnn 2023-01-02 16:11:24 160
en39 English Yunannnn 2023-01-02 16:01:17 43 Tiny change: 'O_. :D\n\n[My so' -> 'O_. :D\n\nBut wait, is there any special cases?\n\n\n[My so'
en38 English Yunannnn 2023-01-02 15:58:41 22
en37 English Yunannnn 2023-01-02 15:57:49 262
en36 English Yunannnn 2023-01-02 15:51:00 40
en35 English Yunannnn 2023-01-02 15:49:41 17 Tiny change: 'x hull. \n\n ![ ](https' -> 'x hull. \n![ ](https'
en34 English Yunannnn 2023-01-02 15:49:27 33 Tiny change: ' ' -> ' '
en33 English Yunannnn 2023-01-02 15:49:11 48
en32 English Yunannnn 2023-01-02 15:48:44 82
en31 English Yunannnn 2023-01-02 15:48:20 37 Tiny change: 'Let your s' -> '![ ](https://i.imgur.com/YeyVfBl.png)Let your s'
en30 English Yunannnn 2023-01-02 15:40:31 41
en29 English Yunannnn 2023-01-02 15:37:15 348
en28 English Yunannnn 2023-01-02 15:35:12 350
en27 English Yunannnn 2023-01-02 15:33:39 62
en26 English Yunannnn 2023-01-02 15:32:31 69
en25 English Yunannnn 2023-01-02 15:30:30 1 Tiny change: 'hull. \n\n[](/predow' -> 'hull. \n\n![](/predow'
en24 English Yunannnn 2023-01-02 15:29:09 68 Tiny change: 'ull. \n\n[](https://' -> 'ull. \n\n[Your text to link here...](https://'
en23 English Yunannnn 2023-01-02 15:15:16 2 Tiny change: 'hull. \n\n(https://c' -> 'hull. \n\n[](https://c'
en22 English Yunannnn 2023-01-02 15:14:48 74 Tiny change: 'hull. \n\n\n\n[My so' -> 'hull. \n\nhttps://mirror.codeforces.com/b373d7/3.png\n\n[My so'
en21 English Yunannnn 2023-01-02 15:14:23 65 Tiny change: 'hull. \n\n\n\n[My so' -> 'hull. \n\nhttps://mirror.codeforces.com/b373d7/3.png\n\n[My so'
en20 English Yunannnn 2023-01-02 15:10:51 109
en19 English Yunannnn 2023-01-02 15:07:14 241
en18 English Yunannnn 2023-01-02 15:05:47 2 Tiny change: 'n(Problem from the ' -> 'n(Problem F from the '
en17 English Yunannnn 2023-01-02 15:05:19 388
en16 English Yunannnn 2023-01-02 14:53:17 243
en15 English Yunannnn 2023-01-02 14:45:49 121
en14 English Yunannnn 2023-01-02 14:41:43 98
en13 English Yunannnn 2023-01-02 14:40:15 757
en12 English Yunannnn 2023-01-02 14:38:45 57
en11 English Yunannnn 2023-01-02 14:37:05 3 Tiny change: 'ALw_wcB#/). \n\nHoweve' -> 'ALw_wcB#/) :D\n\nHoweve'
en10 English Yunannnn 2023-01-02 14:35:58 4 Tiny change: 'w_wcB#/). However, b' -> 'w_wcB#/). \n\nHowever, b'
en9 English Yunannnn 2023-01-02 14:35:37 137
en8 English Yunannnn 2023-01-02 14:31:59 63
en7 English Yunannnn 2023-01-02 14:29:54 267
en6 English Yunannnn 2023-01-02 14:25:46 2 Tiny change: '03470]\n\n<spoil' -> '03470]\n\n\n<spoil'
en5 English Yunannnn 2023-01-02 14:23:29 23
en4 English Yunannnn 2023-01-02 14:21:36 52
en3 English Yunannnn 2023-01-02 14:19:25 45 Tiny change: '03470]\n\n[My so' -> '03470]\n\n<spoiler summary="Tags">\naaa\n</spoiler>\n\n[My so'
en2 English Yunannnn 2023-01-02 14:17:49 112
en1 English Yunannnn 2023-01-02 14:13:47 64 Initial revision (saved to drafts)