题解：AT_abc266_c [ABC266C] Convex Quadrilateral

PeppaPig_qwq · 2024-06-10 17:11:17 · 题解

其他题解用的都是面积来判，这里我还有另一种解法。 根据凸四边形的定义，只要四边形每条边除了顶点以外的另外两个点都在这条边的同一侧就是凸四边形。如果不会判点在边哪一侧，左转这里。 代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long double d;
struct point{
    d x, y;
};
bool left_or_right(point a, point b, point c) {
    d tmp = (b.x - c.x) / (b.y - c.y) * (a.y - c.y) + c.x;
    if (tmp > a.x)
        return 1; //左侧
    return 0;
}

int main() {
    vector<point> pos;
    for (int i = 0; i < 4; i++) {
        point cur;
        cin >> cur.x >> cur.y;
        pos.push_back(cur);
    }
    bool flag = 1;
    for (int i = 0; i < 4; i++) {
        int c = -1;
        for (int j = 0; j < 4; j++) {
            if (i != j and (i + 1) % 4 != j) {
                if (c == -1)
                    c = left_or_right(pos[j], pos[(i + 1) % 4], pos[i]);
                else
                    flag &= (c == left_or_right(pos[j], pos[(i + 1) % 4], pos[i]));
            }
        }
    }
    cout << (flag ? "Yes" : "No");
    return 0;
}