ABC-E K-clinear Line

E - K-colinear Line

座標平面上の N 個の点が与えられます。 1≤i≤N について、i 番目の点の座標は (X i ​ ,Y i ​ ) です。

座標平面上の直線であって、N 個の点のうち K 個以上の点を通るものの個数を求めてください。 ただし、そのようなものが無数に存在する場合は Infinity を出力してください。

３点をとって２本のベクトルを比較するO(N³)はpythonだと無理だと思ったので、辞書を使う方法を検討。間に合わなく反省のために後日再トライ。 ポイントはy軸に衝突刷る切片に有理数で傾きを持つ事と、傾きがゼロのときの枠を用意する事。 小数だと辞書が安定せずWAしたので、1000倍した整数に変更、面倒くさい。

N,K=acinput()
x=[]
for i in range(N):
    x.append(acinput())


x=sorted(x)
from fractions import Fraction

y=defaultdict(int)
for i in range(N-1):
    for j in range(i+1,N):
        v=np.array(x[j])-x[i]
        v=list(v)
        if v[0]==0:
            y[("inf",x[i][0],"inf")]+=1
        else:
            k=-x[i][0]/v[0]
            a=x[i][1]+v[1]*k
            ff=Fraction(v[1],v[0])
            a=str(a*1000)

            y[(a[:3],0,ff.numerator,ff.denominator)]+=1
            #print(x[i],x[j],v,a,ff)

res=0
for k in y:
    n=y[k]
    if K*(K-1)/2<=n:
        res+=1

if K==1:
    print("Infinity")
else:
    print(res)