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

おもしろそうだったのでやってみました。

解答例のように個別に距離を測ってもいいんだけど、距離2の平行線の外側って考えると、計算がちょっと軽くならないかな、と思ってやってみる。

from itertools import combinations
from math import sqrt
from dataclasses import dataclass

@dataclass
class NumberedPoint:
    n: int
    x: float
    y: float
        
DISTANCE = 2.0

def outsiders(points):
    min_outs = [*points]
    
    for p0, p1 in combinations(points, 2):
        tenp_outs = []
        
        if p0.x == p1.x :
            c_smaller = p0.x - DISTANCE
            c_larger = p0.x + DISTANCE
            
            for p2 in points:
                if p2.x <= c_smaller or p2.x >= c_larger :
                    tenp_outs.append(p2)
                if len(tenp_outs) >= len(min_outs):
                    break
                    
        else:
            m = (p1.y - p0.y) / (p1.x - p0.x)  # 傾き
            c = DISTANCE * sqrt(1 + m * m)     # 中心線に加減して平行線にする定数
            c_center = - m * p0.x + p0.y       # 中心線の定数
            c_lower = c_center - c             # 下側の平行線の定数
            c_higher = c_center + c            # 上側の平行線の定数
            
            for p2 in points:
                p_factor = p2.y - m * p2.x
                if p_factor <= c_lower or p_factor >= c_higher :
                    tenp_outs.append(p2)
                if len(tenp_outs) >= len(min_outs):
                    break
                    
        if len(tenp_outs) == 0:
            return []
        if len(tenp_outs) < len(min_outs):
            min_outs = tenp_outs
            
    return min_outs 
    
    
N = int(input())
points = tuple( NumberedPoint(i
                              , *map(float, input().split(" "))
                              )
                for i in range(1, N + 1)
               )    

minimum_outsiders = outsiders(points)

if len(minimum_outsiders) == 0:
    print("none")
else:
    for p in minimum_outsiders:
        print(p.n)

ちょっと速くなったかな?