ABC266 C問題 Convex Quadrilateral【C++, python】

ABC

ABC266のC問題 Convex Quadrilateralを解説します。

ポイント: 時計回りか？反時計回りか？を判定する
「1本目の辺と2本目の辺がつくる角度が時計回りなのか、反時計回りなのか？」を判定できるかということが、解けるか解けないかの分かれ道だったと思います。
ちなみに私は解けませんでした。。

結論としてはベクトルの外積を用いると時計回りか？反時計回りか？を判定できます。
外積は２つのベクトルのつくる平行四辺形の”符号付き面積”と呼ばれるものになります。
その値が負であった場合、時計回り、正であった場合反時計回りとなります。
（つまり、正であるか？負であるか？調べればよいわけです。面積の値は無視していいわけです。）

解答例のコードがどういうことを試しているのかということを一つずつ紙に書き出し計算しています。

入力例

0 0
1 1
-1 0
1 -1

C++での回答例

#include<bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); ++i)

// 座標平面を準備
struct V {
    int x;
    int y;
    V (int x = 0, int y = 0): x(x), y(y) {}
};

int main() {
    vector p(4);
    rep(i, 4) cin >> p[i].x >> p[i].y;  // 入力の受け取り

    rep(i, 4) {
        V A = p[i];         // 1つ目の点をAとする
        V B = p[(i+1)%4];   // 2つ目の点をBとする
        V C = p[(i+2)%4];   // 3つ目の点をCとする

        V AB = {B.x - A.x, B.y - A.y};  // ABベクトル
        V AC = {C.x - A.x, C.y - A.y};  // ACベクトル
        int signed_area = AB.x * AC.y - AB.y * AC.x;    // ABとACのつくる平行四辺形の符号付き面積を計算
        if (signed_area < 0) {          // "符号"の情報のみを利用
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

pythonでの回答例

p = [list(map(int, input().split())) for _ in range(4) ]    # 入力の受け取り

ans = True
for i in range(4):
    a = p[i]        # 1つ目の点をaとする 
    b = p[(i+1)%4]  # 2つ目の点をbとする
    c = p[(i+2)%4]  # 3つ目の点をcとする
    AB = [b[0] - a[0], b[1] - a[1]] # ABベクトル
    AC = [c[0] - a[0], c[1] - a[1]] # ACベクトル
    signed_area = AB[0] * AC[1] - AB[1] * AC[0] # 符号付き面積の計算
    if signed_area < 0: # 符号の情報のみを利用
        ans = False

if ans == True:
    print("Yes")
else:
    print("No")

コメント