๐Ÿšง This website is under construction. ๐Ÿšง
AtCoder
ABC
248
E

ABC
E
Math

ABC248 E - K-colinear Line

https://atcoder.jp/contests/abc248/tasks/abc248_e (opens in a new tab)

colinear ใฏใ€Œๅ…ฑ้€šใฎใ€ใฎๆ„ๅ‘ณใ€‚

็•ฐใชใ‚‹ 3 ็‚นใŒๅŒไธ€็›ด็ทšไธŠใซใ‚ใ‚‹ใ‹ใฎๅˆคๆ–ญใฏใ€ๅ‚พใใงใฏใชใใƒ™ใ‚ฏใƒˆใƒซใ‚’็”จใ„ใ‚‹ไบ‹ใ€‚ๅณใก 3 ็‚น A(x0,y0),B(x1,y1),P(x,y)A(x_0, y_0), B(x_1, y_1), P(x, y) ใŒๅŒไธ€็›ด็ทš็Šถใซใ‚ใ‚‹ใจใ„ใ†ใ“ใจใฏใ€ (AP)โ†’=k(AB)โ†’(AP)^โ†’ = k(AB)^โ†’ ใŒๆˆใ‚Š็ซ‹ใคใ€ใคใพใ‚Š (x1โˆ’x0)(yโˆ’y0)=(y1โˆ’y0)(xโˆ’x0)(x_1-x_0)(y-y_0) = (y_1-y_0)(x-x_0) ใŒๆˆ็ซ‹ใ™ใ‚‹ใ“ใจใงใ‚ใ‚‹ใ€‚

้‡่ค‡ใ‚’ๅ‡ฆ็†ใ™ใ‚‹ใฎใซใ‹ใชใ‚Šๆ‰‹้–“ๅ–ใฃใŸใ€‚ ้›†ๅˆใฏใƒใƒƒใ‚ทใƒฅๅฏ่ƒฝใงใฏใชใ„ใฎใงใ€้›†ๅˆใฎ่ฆ็ด ใซ้›†ๅˆใ‚’ๆŒใคไบ‹ใŒใงใใชใ„ ใใฎใŸใ‚ใ‚ฝใƒผใƒˆใ—ใฆใ‹ใ‚‰ใ‚ฟใƒ—ใƒซใซๅค‰ๆ›ใ—ใฆ้›†ๅˆใซ่ฟฝๅŠ ใ—ใฆใ„ใใŒใ€ใ“ใฎใ‚ฝใƒผใƒˆใŒๅฎŸ่กŒๆ™‚้–“ๅ†…ใซๅŽใพใ‚‹ใ‹ใฉใ†ใ‹ใฏๆญฃ็›ด่‡ชไฟกใŒใชใ‹ใฃใŸ

def colinear_line(x0,y0,x1,y1,x,y):
    return (x1-x0)*(y-y0) == (y1-y0)*(x-x0)
 
n,k_ = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]
 
ans = set()
for i in range(n):
    for j in range(i+1,n):
        group = []
        (x1,y1),(x2,y2) = xy[i],xy[j]
        group.append(i)
        group.append(j)
        for k in range(n):
            if k == i or k == j:
                continue
            x,y = xy[k]
            if colinear_line(x1,y1,x2,y2,x,y):
                group.append(k)
        group = tuple(sorted(group))
        if len(group) >= k_ and group not in ans:
            ans.add(group)
print(len(ans) if k_ != 1 else 'Infinity')