paizaラーニング問題集「部外者をはじけ」を解いてみた

▼考え方

この問題を解くために私が考えた内容1.～3.を以下に示します。

1. 検出したN人のうち任意の2人を選び、2人の座標から直線の方程式を求めます。その直線と、2人以外の人の座標との距離を求めます。距離が2m以上であれば部外者(変数bugai)として情報を保持します。最終的に部外者が最も少ない情報を出力します。

2. 題意より、部外者が1人も存在しなかった場合は文字列noneを出力して処理を終了します。

3. 処理上は検出したN人の番号は0～N-1としているため、(題意に合わせN人の番号を1～Nとするために)出力するときに+1します。

▼コード

########## 処理0(準備) モジュールインポート,インプット,リストや変数定義 ###########

# copy: リストbugaiをリストmin_bugaiへコピーするためのモジュール
import copy

N = int(input())

# xy: 検出したN人の座標を格納するリスト
xy = [list(map(float,input().split(" "))) for i in range(N)]

# bugai: 直線と距離が2m以上離れた人の番号を格納するリスト
bugai = []*(N-2)

# min_bugai: bugaiの要素数が最も少ないものを格納するリスト
min_bugai = [0]*(N)

########## 処理1 任意の2人の座標を結ぶ直線および、その直線と,2人以外の人の座標との距離を求める ###########

# 考え方1.
for i in range(N):

    for j in range(i+1,N):
        
        a = xy[j][1] - xy[i][1]
        b = xy[j][0] - xy[i][0]
        c = b*xy[i][1] - a*xy[i][0]
        
        for k in range(N):
            
            if k != i and k != j:
            
                d = abs(a*xy[k][0]-b*xy[k][1]+c) / (a**2+b**2)**0.5
                
                if d >= 2:
                    bugai.append(k)

        # 考え方2.
        if len(bugai) == 0:
            print("none")
            exit()
            
        elif len(bugai) < len(min_bugai):
            min_bugai = copy.deepcopy(bugai)
            
        bugai = []*(N-2)

# 考え方3.
[print(i+1) for i in min_bugai]