![見出し画像](https://assets.st-note.com/production/uploads/images/38063756/rectangle_large_type_2_9447ced0d612c128f7dc967c31627eb3.jpg?width=1200)
AtCoder Beginner Contest 181を見返す
全体
開始30分でA,B問題に正解できたんですが、C問題でWAが1つ出てしまいACできないまま時間切れになりました。AtCoder Problemsをみると今回はC問題灰色、D問題茶色なんですね。問題を見ることも出来ていないですがD問題もどこかで挑戦したいです。
今回はC問題を見直します。
C - Collinearity
問題
3個以上100個未満の座標が与えられるので、同一直線上に3点が並ぶ場合は「Yes」、並ばない場合は「No」を出力する問題
後日作成したコード
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ans = "No"
for i in range(n):
x1, y1 = xy[i][0], xy[i][1]
for j in range(i+1, n):
x2, y2 = xy[j][0], xy[j][1]
if x1 == x2 or y1 == y2: k1 = 0
else:
k1 = (y2-y1)/(x2-x1)
for k in range(j+1, n):
x3, y3 = xy[k][0], xy[k][1]
if x1 == x2 == x3 or y1 == y2 == y3: ans = "Yes"
if x1 == x3 or y1 == y3: continue
k2 = (y3-y1)/(x3-x1)
if k1 == k2: ans = "Yes"
if ans == "Yes": break
if ans == "Yes": break
if ans == "Yes": break
print(ans)
与えられる座標の数が最大でも100、よって組み合わせの数は最大でも100c3=161,700です。計算量は10^6程度まで許されているので、この問題は全検索で解答します。
点A, B, Cがある場合、点A,Bを通る直線ABと,点A,Cを通る直線ACの傾きが同じであれば3点が同一直線上にあると言えます。傾きを求めるのは以下の様に行います。
傾き = (yの増加量)/(xの増加量)
なので、A(x1, y1), B(x2, y2)の場合
直線ABの傾き = (y2-y1)/(x2-x1)
上記のコードでは直線ACの場合も同様に傾きを求め、ABの傾きと同値であれば「Yes」を出力する様にしています。X軸やY軸に並行な直線の場合は0除算エラーが出るため、傾きに0を代入する様にしています。
コンテスト中のWAは直線がx軸と並行な場合が考慮漏れしていたために起こっていました。Y軸並行はサンプルにあったので思い付いたんですが、X軸並行の場合は思いつけなかったです、Y軸とX軸はペアで考えてX軸並行の処理も思いつける様になりたい。。。。
この記事が気に入ったらサポートをしてみませんか?