PAST013J 解法 部分問題: 直線 \(l\) を固定したとき 直線\(l: ax + by = c\) で,平面が2つの領域に分割される. 2点 \(P,Q\) が,同じ領域に属しているかを判定する. 同じなら直線を通らなくて済むし, 異なるなら直線を通らないといけない. 2つの領域は \(ax + by > c\) と \(ax + by < c\) に分けられるので, これで判定ができる. 本問題 通らなくて良い直線のコストを 0で置き直して コスト全体をソートして,小さい方から \(K\) 個選ぶのが最適. 使っている記号,マクロ等 "https://ecsmtlir.haten…