役人
题意翻译
题目描述
你是被河流和绿色包围的小而富裕的王国的官员。
因为这个国家没有明确规定土地的边界线，所以围绕土地所有权的纷争不断。
被新国王指示解决这个问题的你决定了用地的边界线。
因为你负责的地方有300棵大树，所以我选了这个作为记号。
每片土地都是3棵树的三角形。
因为王国的居民都很关心隐私，所以有必要一点都不涉及土地的界限。
即不能共享地基的边界线或共享地基的拐角。
当然，不能发生用地重叠的情况。
尽可能满足这个条件。
题目描述
[problemUrl]: https://atcoder.jp/contests/geocon2013/tasks/geocon2013_a
あなたは、川と緑に囲まれた小さいながらも豊かな王国の役人です。
この国では敷地の境界線をきちんと決めていなかったため土地の所有権をめぐる争いが絶えませんでした。
新しい王からこの問題を解決するように指示されたあなたは敷地の境界線を決めることにしました。
あなたが担当している地域に大きめの木が300本あったのでこれを目印にすることにしました。
それぞれの敷地は3つの木を選んでできる三角形の形をしています。
王国の住人はプライバシーに気を使うので敷地の境界が少しも触れていないようにする必要があります。
すなわち、敷地の境界線を共有していたり、敷地の角を共有していてはいけません。
もちろん、敷地が重なることがあってはなりません。
この条件を満たしつつ敷地の数を最大化しましょう。
入力は以下の形式で標準入力から与えられる。 > $ X1\ Y1 $ $ X2\ Y2 $ $ ... $ $ X300\ Y300 $
- $ i $ 番目の木の座標を表す整数 $ Xi\ Yi\ (1\ ≦\ i\ ≦\ 300\ ,\ -1000\ ≦\ Xi,Yi\ ≦\ 1000) $ が空白区切りで $ 300 $ 行与えられる。
- ただし、3本の木が一直線上に並ぶことはない。
出力は以下の形式で標準出力から出力すること。 > $ N $ $ p1,1\ p1,2\ p1,3 $ $ p2,1\ p2,2\ p2,3 $ $ ... $ $ pN,1\ pN,2\ pN,3 $
- 1行目には境界を決めた敷地の数 $ N $ を出力すること。
- 2行目からN+1行目にはそれぞれの敷地を決めるのに使った3本の木の番号を空白区切りで出力すること。ただし、木の番号とは入力で与えられる順番のことであり、1〜300である。
- 各行の最後には改行を出力すること。
この問題の点数は決めた敷地の数 $ N $ によって計算されます。
各テストケースについて $ N\ /\ 100 $ が点数になります。
ただし出力が制約を満たさない場合、そのテストケースについての点数は $ 0 $ になります。
テストケースは100ケースあります。
```
-724 -666
849 411
820 769
-86 -961
972 530
-735 412
254 -106
-460 146
-221 -816
776 -979
549 -469
117 59
-442 587
199 -95
-664 -303
-376 340
-169 248
-53 496
332 -875
763 833
510 -758
-219 306
933 -192
860 467
75 -89
-697 346
912 -194
450 436
426 215
-737 285
479 -440
98 -759
-493 95
646 -126
-343 742
-573 45
-930 -511
-681 -439
538 -293
-698 198
-519 855
238 -48
-46 -815
70 -896
-15 464
-534 -921
-573 -448
922 -706
-434 -466
-171 989
205 538
168 -538
429 292
-871 -510
739 -829
-423 -384
498 43
-501 -589
894 -910
-757 -238
531 326
390 -82
763 -858
334 659
-972 409
-723 -182
395 -551
-485 580
-654 214
-515 -646
-541 -852
-305 -84
742 145
507 833
332 870
847 635
992 -329
3 -614
-654 390
-261 -590
868 882
834 -417
50 -149
-801 -341
-898 -887
-93 -427
850 -508
59 -109
-321 -627
724 876
360 621
-433 312
-190 -266
641 -914
581 -541
448 946
-230 605
-472 510
577 -559
-416 -253
594 53
-734 990
192 -744
-828 -148
-94 -402
-464 -779
132 -81
914 -952
-60 -976
-65 -556
-107 -677
-895 -163
-450 611
474 468
-722 888
-971 481
-15 -359
30 -879
813 -775
-441 -72
834 798
693 -308
762 460
809 12
71 709
375 -115
-528 52
341 529
248 414
914 -103
-223 -62
999 -300
641 743
835 892
477 78
825 -232
-636 -81
-696 -286
-677 721
-209 -797
-971 66
-610 264
812 773
-740 578
129 -177
-59 940
86 -613
-580 921
-820 -679
-812 238
315 -225
777 206
338 -549
-244 385
502 887
-344 487
997 -82
919 -963
-78 932
602 227
762 705
486 281
-105 -10
937 -571
116 152
838 140
-746 -984
783 417
-161 -685
-641 129
69 351
982 153
-780 5
405 184
-122 237
116 -147
643 626
-676 -763
264 644
-696 -944
823 923
500 -373
290 -386
-622 738
-137 -555
-604 -613
-873 732
170 905
-247 -118
124 657
389 292
-108 791
494 -758
-129 745
170 -568
212 120
-148 52
-302 -991
26 -237
-114 -361
485 43
-376 1000
668 -570
-99 -818
610 -74
-133 -457
-553 -178
-467 -465
-93 -270
-384 586
-321 -780
598 -890
261 724
-902 -152
645 994
-767 61
-693 70
-383 -211
990 632
404 -975
263 -853
-470 -654
621 965
-144 -595
-755 554
-917 -386
202 497
-712 260
-526 89
-464 -990
-352 -513
-116 754
708 356
-623 -642
860 -915
28 -205
-21 824
-539 -333
391 741
205 -77
524 -380
858 -483
965 -799
-744 -79
248 15
-962 -571
-938 243
-420 -484
-883 851
18 -700
211 660
694 122
877 390
188 -154
676 -33
259 957
378 -142
624 -860
-855 864
771 -969
601 29
-140 -241
154 384
933 619
-555 732
-368 -299
128 487
-318 220
-964 -175
-994 -573
910 36
497 88
-230 -535
963 683
-714 -150
-835 -151
569 506
-525 -339
896 570
802 497
508 908
-105 570
-625 -383
-786 517
309 118
643 644
649 111
-501 188
-762 317
-250 406
-367 344
-892 568
199 688
54 942
-855 -697
-141 -695
340 -137
-965 -54
442 -108
-729 90
```
```
10
81 294 215
89 166 169
158 43 172
3 259 41
293 76 29
84 214 249
284 287 178
270 149 1
171 125 68
299 273 257
```