A - 役人
Editorial
/
入力は以下の形式で標準入力から与えられる。
出力は以下の形式で標準出力から出力すること。
Time Limit: 2 sec / Memory Limit: 64 MB
問題文
あなたは、川と緑に囲まれた小さいながらも豊かな王国の役人です。
この国では敷地の境界線をきちんと決めていなかったため土地の所有権をめぐる争いが絶えませんでした。
新しい王からこの問題を解決するように指示されたあなたは敷地の境界線を決めることにしました。
あなたが担当している地域に大きめの木が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
出力例の場合、このケースのポイントは 10 / 100 = 0.10 になります。