AtCoder Beginner Contest 422 vp

AtCoder Beginner Contest 422

Colinear

注意到要求至少一般的点都出现在直线上，那么随机选两个点在最终的直线上的概率为0.25，因此随机选20个点判断它们形成的直线是否满足条件即可。

n=R()
nums=[]

for i in range(n):
    nums.append(RR())

i=0
while i<20:
    a=randint(0,n-1)
    b=randint(0,n-1)
    if a==b:continue
    i+=1
    x1,y1=nums[a]
    x2,y2=nums[b]

    a=y2-y1
    b=x1-x2
    c=(x2-x1)*y1-(y2-y1)*x1
    cnt=0
    for x,y in nums:
        if a*x+b*y+c==0:
            cnt+=1
        if cnt>=ceil(n/2):
            print('Yes')
            print(a,b,c)
            exit(0)
print('No')