108學年度資訊能力競賽(北二區 【新竹高中考區 】 PM 第1題 射飛機)

 

Python Code：

#n個點座標

n=int(input())

#每的點的座標

k=[] # 存入基地台位置

for i in range(n):

    q=[int(x) for x in input().split()] 

    k.append(q)

#求最大公因數

def gcd(x, y):

    return x if y== 0 else gcd(y, x % y)

#輸入點傳回直線係數

def line(p,q):

    A=q[1]-p[1]

    B=-(q[0]-p[0])

    C=p[1]*(q[0]-p[0])-p[0]*(q[1]-p[1])

    d=gcd(gcd(A,B),C)

    a=A//d

    b=B//d

    c=C//d

    if a>0:

        return [-a/b,a,b,c]

    elif a==0:

        if b>0:

            return [0,0,b,c]

        elif b<0:

            return [0,0,-b,-c]

            

    else:

        return [-a/b,-a,-b,-c]

ans=[]#存斜率及a,b,c值

for i in range(n-1):

    for j in range(i+1,n):

        ans.append(line(k[i],k[j]))

slope=[]

for i in range(len(ans)):

    slope.append(ans[i][0])

slope_min=min(slope)

for i in range(1,4):

    print(ans[slope.index(slope_min)][i],end=' ')