题解：AT_abc266_c [ABC266C] Convex Quadrilateral

kebibulainente · 2024-06-25 23:04:21 · 题解

ABC266C 题解

题目传送门

思路：

计算四边形面积 s 和四边形四个顶点构成的三个三角形中面积最大值，就好了！

难点（警告）：

在如何判断四边形是否为凹四边形。可以发现如果是凹四边形那么就会有一个三角形大于原四边形，并且正好等于剩下三个三角形之和，因此便可以使用这一性质判断凹四边形。

主要程序：

 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]));
            }
        }
    }