題義是給N個點，點的座標都是整數。求出所有包含三點以上的線，線用點的集合表示 一個點可以屬於多條線。注意：線不是線段，是無限延伸的，而線段為線的一個區間。。
這一題的想法如下：對所有的點配對，可以算出 N * (N - 1) 個線段，只要能知道共線的線段再group起來即可。由於線段必為線的一部份，共線的線段必有相同的線表示式。所以重點在線的表示式，點斜式可以滿足我們的需求，點即為線y軸的交點 (x = 0)。如果斜率無限大，則是用x軸的交點。
不過考慮到floating precision，斜率會有誤差。再grouping時的相等比較會麻煩些。小技巧是，由於點座標都是整數，所以可以用最 簡分數表達斜率(差值再除以gcd)，如此一來，即可直接比較相等與否。所以只要把所有線段sort一遍，把同組的線段湊起來( 斜率分數exact 相等，交點誤差小於某個epsilon)，整理一下即可。
話雖如此，還是難以一次寫對。第一次錯在沒有把斜率用分數表達，第二次錯在最簡分數沒有考慮 0 / 5 應該表達為 0 / 1的情況....唉
備份測資
5 5 8 7 14 11 4 8 20 15 12 6 18 21 0 0
5 5 8 8 14 13 0 0
5 5 25 17 20 23 10 11 20 14 15 11 0 0
1 1 2 1 3 1 1 2 2 2 3 2 1 3 2 3 3 3 0 0
1 0 2 0 3 0 0 0
0 1 0 2 0 3 0 0
1 1 1 2 1 3 1 4 2 1 3 1 4 1 4 2 4 3 4 4 2 4 3 4 0 0
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 0 0
0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
2 9999 1 9999 0 9999 0 9998 1 9998 2 9998 1 9997 0 9997 2 9997 4999 5001
5000 5001 4999 5000 5001 5001 5000 5000 4999 4999 5001 5000 5000 4999
5001 4999 9997 9997 9997 9998 9998 9997 9997 9999 9998 9998 9999 9997
9998 9999 9999 9998 9999 9999 9999 0 9999 1 9999 2 9998 0 9998 1 9998 2
9997 0 9997 1 9997 2 5000 1 1 5000 9998 5000 5000 9998 0 0
1 314 8610 2026 2729 6716 3187 1618 3723 4257 821 4748 706 8408 598 2933
9172 3679 7746 3279 6977 8441 7180 3067 1627 3295 4660 2467 8256 2791 4818 1492
8743 2873 7727 9764 4925 8879 8272 203 1411 1435 5008 217 5929 97 7745 6506
7705 7081 5575 2061 6811 5928 9554 6440 9983 2438 6761 2957 859 7723 4953 8816
5100 5733 9531 6848 3387 77 7053 9889 7740 7495 1977 1437 9136 7842 5893 8647
6894 2879 937 6289 2800 8771 1613 2732 5437 9607 1744 1571 2681 1775 5768 4982
2852 1560 6098 7397 7464 804 764 598 1066 7955 8059 3816 6120 4368 7408 4939
3413 8188 8170 1414 935 672 603 1939 6729 2275 5703 2545 3659 8371 3146 3149
6564 6922 9030 3187 4787 2965 7667 7405 5520 7236 4117 5421 3663 7550 6689 1124
4717 4037 1148 539 5486 6734 1543 3376 8387 6814 9270 2773 7009 7345 5000 6638
3583 7626 9465 3649 1267 9869 3063 545 1020 8667 5544 6971 1007 6688 166 3099
9043 5352 2921 7395 9006 3472 3538 4878 716 8508 7603 1804 9228 4936 1276 8923
4033 2076 3294 4651 1099 6232 9276 5406 3261 4483 2268 1847 6905 9960 6297 6916
5407 973 3483 7721 2330 8803 7138 4388 9803 1545 394 1844 97 3788 3949 3638
823 4538 5047 4606 6754 8175 5669 2534 3724 5826 8744 6080 2572 6969 5577 8787
3609 3640 6217 7800 4570 2054 6982 8372 7518 9018 1865 7755 2675 2955 7028 4569
9642 1885 123 2245 8991 3228 8629 7631 9666 2744 3961 8361 209 2470 528 5077
4227 4 1502 7093 3125 3954 5477 2610 1511 2930 770 7056 3303 7892 6551 5661
3415 5267 2560 8850 6845 324 1580 1556 4130 4189 1437 38 5297 7623 5703 2308
8624 620 4852 751 3671 6641 2059 8037 5213 4187 393 9920 1605 465 589 1014
8034 9544 1152 2134 7635 9801 3360 4967 3414 5231 9223 5111 6600 9995 7690 7158
8941 9948 7327 7815 168 3660 3198 748 7837 2601 2985 7531 485 8943 9242 4883
6890 3781 4221 7466 6961 3411 6294 5100 9688 1011 1553 3383 6164 3561 5105 6463
8102 6359 9517 4985 4854 9960 2392 1989 4377 6893 7590 322 6127 8003 4643 1684
6345 748 9623 7873 8701 4303 58 2218 5772 8825 586 4742 9314 8699 8596 7213
9812 2127 1542 6613 8251 1898 173 8165 5607 4689 4392 1489 7999 8728 957 5983
7994 2172 4746 4039 5020 7038 7809 3158 352 6047 2920 587 3333 4835 843 6556
8557 3429 3054 4712 9163 7234 3351 4923 8085 2520 364 3480 8848 8607 4377 2507
4215 3687 6506 4299 6359 7582 8128 4559 5375 6160 3078 2402 4083 7244 6556 1795
9604 355 3237 8946 4673 5140 8775 6730 4148 5825 1448 9751 4704 1536 3131 6138
8164 4834 1353 4651 1443 3306 6623 8218 8569 1555 1768 7471 2759 3441 2478 390
9003 6896 805 6640 146 6188 5816 7709 1915 8947 8116 6416 4876 7814 7475 1913
3781 9057 5266 8744 7277 2987 5935 1087 3446 3530 4228 5735 9137 6791 7380 9955
3582 953 4004 2773 9226 2362 3880 807 5285 5139 5372 2242 1956 4152 9699 5026
5787 3710 3758 7887 9149 6811 5735 5272 9293 2290 227 9790 4950 9705 2069 8265
953 4329 612 9978 3845 7047 8653 8209 3941 6556 2752 8652 1818 3661 4124 828
9683 51 1870 1043 628 6369 2726 8039 1186 6943 4066 4890 5211 1003 9378 3248
43 3306 143 3376 153 3383 0 0
0 0
測資解答
The following lines were found:
( 4, 8)( 8, 7)( 12, 6)
( 5, 5)( 8, 7)( 14, 11)( 20, 15)
( 12, 6)( 14, 11)( 18, 21)
No lines were found
The following lines were found:
( 5, 5)( 10, 11)( 20, 23)
( 5, 5)( 15, 11)( 20, 14)( 25, 17)
The following lines were found:
( 1, 1)( 1, 2)( 1, 3)
( 1, 1)( 2, 1)( 3, 1)
( 1, 1)( 2, 2)( 3, 3)
( 1, 2)( 2, 2)( 3, 2)
( 1, 3)( 2, 2)( 3, 1)
( 1, 3)( 2, 3)( 3, 3)
( 2, 1)( 2, 2)( 2, 3)
( 3, 1)( 3, 2)( 3, 3)
The following lines were found:
( 1, 0)( 2, 0)( 3, 0)
The following lines were found:
( 0, 1)( 0, 2)( 0, 3)
The following lines were found:
( 1, 1)( 1, 2)( 1, 3)( 1, 4)
( 1, 1)( 2, 1)( 3, 1)( 4, 1)
( 1, 4)( 2, 4)( 3, 4)( 4, 4)
( 4, 1)( 4, 2)( 4, 3)( 4, 4)
The following lines were found:
( 1, 1)( 1, 2)( 1, 3)
( 1, 1)( 2, 1)( 3, 1)
( 1, 1)( 2, 2)( 3, 3)
( 1, 2)( 2, 2)( 3, 2)
( 1, 3)( 2, 2)( 3, 1)
( 1, 3)( 2, 3)( 3, 3)
( 2, 1)( 2, 2)( 2, 3)
( 3, 1)( 3, 2)( 3, 3)
The following lines were found:
( 0, 1)( 0, 2)( 0,9997)( 0,9998)( 0,9999)
( 0, 1)( 1, 1)( 2, 1)(5000, 1)(9997, 1)(9998, 1)(9999, 1)
( 0, 1)( 1, 2)(4999,5000)(5000,5001)(9997,9998)(9998,9999)
( 0, 1)( 1,5000)( 2,9999)
( 0, 1)( 2, 2)(9998,5000)
( 0, 1)(4999,4999)(9998,9997)
( 0, 2)( 1, 1)( 2, 0)
( 0, 2)( 1, 2)( 2, 2)(9997, 2)(9998, 2)(9999, 2)
( 0, 2)( 1,5000)( 2,9998)
( 0, 2)(4999,5000)(9998,9998)
( 0, 2)(4999,5001)(9997,9999)
( 0,9997)( 1,9997)( 2,9997)(9997,9997)(9998,9997)(9999,9997)
( 0,9997)( 1,9998)( 2,9999)
( 0,9997)(4999,4999)(9998, 1)
( 0,9998)( 1,5000)( 2, 2)
( 0,9998)( 1,9997)(4999,4999)(9997, 1)(9998, 0)
( 0,9998)( 1,9998)( 2,9998)(5000,9998)(9997,9998)(9998,9998)(9999,9998)
( 0,9998)(4999,5000)(9998, 2)
( 0,9999)( 1,5000)( 2, 1)
( 0,9999)( 1,9998)( 2,9997)(4999,5000)(5000,4999)(9997, 2)(9998, 1)(9999, 0)
( 0,9999)( 1,9999)( 2,9999)(9997,9999)(9998,9999)(9999,9999)
( 0,9999)( 2,9998)(9998,5000)
( 1, 0)( 1, 1)( 1, 2)( 1,5000)( 1,9997)( 1,9998)( 1,9999)
( 1, 0)( 2, 0)(9997, 0)(9998, 0)(9999, 0)
( 1, 0)( 2, 1)(5000,4999)(5001,5000)(9998,9997)(9999,9998)
( 1, 0)( 2, 2)(5000,9998)
( 1, 0)(4999,4999)(9997,9998)
( 1, 0)(5000, 1)(9999, 2)
( 1, 1)( 2, 2)(4999,4999)(5000,5000)(5001,5001)(9997,9997)(9998,9998)(9999,9999)
( 1, 1)(4999,5000)(9997,9999)
( 1, 1)(5000,4999)(9999,9997)
( 1, 2)(5000, 1)(9999, 0)
( 1, 2)(5000,5000)(9999,9998)
( 1,5000)(4999,5000)(5000,5000)(5001,5000)(9998,5000)
( 1,5000)(9997, 2)(9999, 1)
( 1,5000)(9997,9998)(9999,9999)
( 1,9997)(5000,4999)(9999, 1)
( 1,9997)(5000,9998)(9999,9999)
( 1,9998)(4999,4999)(9997, 0)
( 1,9998)(5000,5000)(9999, 2)
( 1,9999)( 2,9997)(5000, 1)
( 1,9999)( 2,9998)(4999,5001)(5000,5000)(5001,4999)(9998, 2)(9999, 1)
( 1,9999)(4999,5000)(9997, 1)
( 1,9999)(5000,9998)(9999,9997)
( 2, 0)( 2, 1)( 2, 2)( 2,9997)( 2,9998)( 2,9999)
( 2, 0)(5000, 1)(9998, 2)
( 2, 0)(5000,4999)(9998,9998)
( 2, 0)(5001,4999)(9999,9997)
( 2, 1)(5000,5000)(9998,9999)
( 2, 2)(5000, 1)(9998, 0)
( 2,9997)(5000,9998)(9998,9999)
( 2,9998)(5000,4999)(9998, 0)
( 2,9999)(5000,5000)(9998, 1)
( 2,9999)(5000,5001)(5001,5000)(9999, 2)
( 2,9999)(5000,9998)(9998,9997)
(4999,4999)(4999,5000)(4999,5001)
(4999,4999)(5000,4999)(5001,4999)
(4999,5001)(5000,5001)(5001,5001)
(5000, 1)(5000,4999)(5000,5000)(5000,5001)(5000,9998)
(5000, 1)(9998,9997)(9999,9999)
(5000,9998)(9998, 2)(9999, 0)
(5001,4999)(5001,5000)(5001,5001)
(9997, 0)(9997, 1)(9997, 2)(9997,9997)(9997,9998)(9997,9999)
(9997, 0)(9998, 1)(9999, 2)
(9997, 1)(9998,5000)(9999,9999)
(9997, 2)(9998,5000)(9999,9998)
(9997,9998)(9998,5000)(9999, 2)
(9997,9999)(9998,5000)(9999, 1)
(9997,9999)(9998,9998)(9999,9997)
(9998, 0)(9998, 1)(9998, 2)(9998,5000)(9998,9997)(9998,9998)(9998,9999)
(9999, 0)(9999, 1)(9999, 2)(9999,9997)(9999,9998)(9999,9999)
The following lines were found:
( 43,3306)( 143,3376)( 153,3383)
(1443,3306)(1543,3376)(1553,3383)
(3261,4483)(3294,4651)(3415,5267)
(3261,4483)(3333,4835)(3351,4923)(3360,4967)(3414,5231)
(3303,7892)(3483,7721)(3583,7626)(3663,7550)
