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

Правка en16, от Yunannnn, 2023-01-02 14:53:17

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 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 ai 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 read some hints!

Tags

My solution

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en61 Английский Yunannnn 2023-01-02 17:30:31 0 (published)
en60 Английский Yunannnn 2023-01-02 17:29:27 8 Tiny change: ' return — 1;\n }' -> ' return - 1;\n }'
en59 Английский Yunannnn 2023-01-02 17:28:04 64
en58 Английский Yunannnn 2023-01-02 17:22:47 5
en57 Английский Yunannnn 2023-01-02 17:20:54 452
en56 Английский Yunannnn 2023-01-02 17:11:12 21
en55 Английский Yunannnn 2023-01-02 17:10:04 440
en54 Английский Yunannnn 2023-01-02 16:58:51 106
en53 Английский Yunannnn 2023-01-02 16:55:07 249
en52 Английский Yunannnn 2023-01-02 16:47:19 54
en51 Английский Yunannnn 2023-01-02 16:46:19 3 Tiny change: ' **N** is 10^6.\n</spoil' -> ' **N** is $10^6$.\n</spoil'
en50 Английский Yunannnn 2023-01-02 16:45:11 320
en49 Английский Yunannnn 2023-01-02 16:38:11 53
en48 Английский Yunannnn 2023-01-02 16:34:18 197
en47 Английский Yunannnn 2023-01-02 16:27:25 40
en46 Английский 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 Английский Yunannnn 2023-01-02 16:24:27 15 Tiny change: 'j1L69y)\n<spoiler' -> 'j1L69y)\n</spoiler>\n\n<spoiler'
en44 Английский Yunannnn 2023-01-02 16:23:32 151
en43 Английский Yunannnn 2023-01-02 16:18:04 1453
en42 Английский Yunannnn 2023-01-02 16:14:21 9703
en41 Английский Yunannnn 2023-01-02 16:12:02 3 Tiny change: 'so easy.\n![ ](htt' -> 'so easy.\n\n![ ](htt'
en40 Английский Yunannnn 2023-01-02 16:11:24 160
en39 Английский 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 Английский Yunannnn 2023-01-02 15:58:41 22
en37 Английский Yunannnn 2023-01-02 15:57:49 262
en36 Английский Yunannnn 2023-01-02 15:51:00 40
en35 Английский Yunannnn 2023-01-02 15:49:41 17 Tiny change: 'x hull. \n\n ![ ](https' -> 'x hull. \n![ ](https'
en34 Английский Yunannnn 2023-01-02 15:49:27 33 Tiny change: ' ' -> ' '
en33 Английский Yunannnn 2023-01-02 15:49:11 48
en32 Английский Yunannnn 2023-01-02 15:48:44 82
en31 Английский Yunannnn 2023-01-02 15:48:20 37 Tiny change: 'Let your s' -> '![ ](https://i.imgur.com/YeyVfBl.png)Let your s'
en30 Английский Yunannnn 2023-01-02 15:40:31 41
en29 Английский Yunannnn 2023-01-02 15:37:15 348
en28 Английский Yunannnn 2023-01-02 15:35:12 350
en27 Английский Yunannnn 2023-01-02 15:33:39 62
en26 Английский Yunannnn 2023-01-02 15:32:31 69
en25 Английский Yunannnn 2023-01-02 15:30:30 1 Tiny change: 'hull. \n\n[](/predow' -> 'hull. \n\n![](/predow'
en24 Английский Yunannnn 2023-01-02 15:29:09 68 Tiny change: 'ull. \n\n[](https://' -> 'ull. \n\n[Your text to link here...](https://'
en23 Английский Yunannnn 2023-01-02 15:15:16 2 Tiny change: 'hull. \n\n(https://c' -> 'hull. \n\n[](https://c'
en22 Английский 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 Английский 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 Английский Yunannnn 2023-01-02 15:10:51 109
en19 Английский Yunannnn 2023-01-02 15:07:14 241
en18 Английский Yunannnn 2023-01-02 15:05:47 2 Tiny change: 'n(Problem from the ' -> 'n(Problem F from the '
en17 Английский Yunannnn 2023-01-02 15:05:19 388
en16 Английский Yunannnn 2023-01-02 14:53:17 243
en15 Английский Yunannnn 2023-01-02 14:45:49 121
en14 Английский Yunannnn 2023-01-02 14:41:43 98
en13 Английский Yunannnn 2023-01-02 14:40:15 757
en12 Английский Yunannnn 2023-01-02 14:38:45 57
en11 Английский Yunannnn 2023-01-02 14:37:05 3 Tiny change: 'ALw_wcB#/). \n\nHoweve' -> 'ALw_wcB#/) :D\n\nHoweve'
en10 Английский Yunannnn 2023-01-02 14:35:58 4 Tiny change: 'w_wcB#/). However, b' -> 'w_wcB#/). \n\nHowever, b'
en9 Английский Yunannnn 2023-01-02 14:35:37 137
en8 Английский Yunannnn 2023-01-02 14:31:59 63
en7 Английский Yunannnn 2023-01-02 14:29:54 267
en6 Английский Yunannnn 2023-01-02 14:25:46 2 Tiny change: '03470]\n\n<spoil' -> '03470]\n\n\n<spoil'
en5 Английский Yunannnn 2023-01-02 14:23:29 23
en4 Английский Yunannnn 2023-01-02 14:21:36 52
en3 Английский 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 Английский Yunannnn 2023-01-02 14:17:49 112
en1 Английский Yunannnn 2023-01-02 14:13:47 64 Initial revision (saved to drafts)