← 返回题目列表

AtCoder · geocon2013_a

A. 官方

中文机器翻译题面 查看原题

問題文

你是一个小而富裕的王国的官员,周围环绕着河流和绿色植物。
在这个国家,土地边界没有明确界定,因此土地所有权纠纷不断。
新国王指示您解决这个问题,您决定定义您的财产边界。

你负责的区域有300棵大树,所以你决定用它们作为地标。
每个地点的形状都像由三棵选定的树组成的三角形。
王国居民关心自己的隐私,因此有必要确保财产边界完全不接触。
换句话说,它们不得共享物业线或角落。
当然,站点不能重叠。
在满足这些条件的同时最大化站点数量。 一个整数,表示第


入力

输入是按以下格式从标准输入给出的。
X1 Y1
X2 Y2
...
X300 Y300
  • i 棵树的坐标 Xi Yi (1 ≦ i ≦ 300 , -1000 ≦ Xi,Yi ≦ 1000) 由空格分隔。 给出了 300 行。
  • 然而,三棵树永远不会排成一条直线。

出力

输出应按以下格式从标准输出输出。
N
p1,1 p1,2 p1,3
p2,1 p2,2 p2,3
...
pN,1 pN,2 pN,3
  • 第一行显示有边界的站点数量。 输出 N 。
  • 从第二行到第N+1行,输出用于确定每个站点的三棵树的编号,以空格分隔。但是,树编号是输入中给出的顺序,为 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

对于示例输出,本例中的点是 10 / 100 = 0.10 。