#geocon2013a. [geocon2013_a]役人

[geocon2013_a]役人

问题文

您是一个身处环绕着河流和绿色的小而富饶的王国的官员。
由于该国没有明确规定土地边界线,因此土地所有权的争议不断。
新国王指示您解决这个问题,您决定确定土地的边界线。

由于您负责的地区有300棵大树,因此您决定以它们作为标志。
每个地块都由选择的3棵树组成三角形。
由于王国的居民注重隐私,因此地块的边界线不能有任何接触。
也就是说,地块之间不能共享边界线或角落。
当然,地块不能重叠。
在满足这些条件的同时,让我们尽可能地增加地块数。


输入

输入将通过标准输入提供,格式如下。X1Y1X1 Y1 X2Y2X2 Y2 ...... X300Y300X300 Y300

  • 每行包含一个整数对 XiYi(1i300,1000Xi,Yi1000)Xi Yi (1 ≤ i ≤ 300, -1000 ≤ Xi,Yi ≤ 1000),表示第 ii 棵树的坐标。
  • 注意,这3棵树不会共线。

输出

输出将通过标准输出提供,格式如下。NN p1,1p1,2p1,3p1,1 p1,2 p1,3 p2,1p2,2p2,3p2,1 p2,2 p2,3 ...... pN,1pN,2pN,3pN,1 pN,2 pN,3

  • 第一行输出确定的地块数量 NN
  • 从第二行到第 N+1 行,每行输出用于确定每个地块的3棵树的编号,以空格分隔。树的编号是按照输入顺序给出的,从1到300。
  • 每行末尾输出换行符。

部分分

本问题的得分取决于确定的地块数量 NN,每个测试用例得分为 N/100N / 100。 如果输出不符合约束条件,则该测试用例得分为 00。 共有 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