[ABC266C] Convex Quadrilateral 题解

2020luke · 2024-01-18 10:59:22 · 题解

[ABC266C] Convex Quadrilateral 题解

思路解析

此题思路难点就在如何判断四边形是否为凹四边形，强行计算角度需要使用三角函数公式，过于复杂，于是就需要转换思路。可以发现如果是凹四边形那么就会有一个三角形大于原四边形，并且正好等于剩下三个三角形之和，因此便可以使用这一性质判断凹四边形。

如下图，此时 \Delta ABC + \Delta ACD + \Delta BCD = \Delta ABD，是凹四边形。

而对于计算面积公式的方法就很多种多样，可以采用公式法和割补法。割补法即为给原三角形套上一个大长方形，然后减去空白部分即可。如图。

code

割补法计算面积部分：

int s(int xa, int ya, int xb, int yb, int xc, int yc) {
    int mnx = min({xa, xb, xc});
    int mxx = max({xa, xb, xc});
    int mny = min({ya, yb, yc});
    int mxy = max({ya, yb, yc});
    int tot = (mxx - mnx) * (mxy - mny) * 2;
    int tri1 = abs(xa - xb) * abs(ya - yb);
    int tri2 = abs(xb - xc) * abs(yb - yc);
    int tri3 = abs(xa - xc) * abs(ya - yc);
    int rec1 = min((abs(xa - xb)) * abs(ya - yc), abs(xa - xc) * abs(ya - yb)) * 2;
    int rec2 = min((abs(xa - xb)) * abs(yb - yc), abs(xb - xc) * abs(ya - yb)) * 2;
    int rec3 = min((abs(xb - xc)) * abs(ya - yc), abs(xa - xc) * abs(yb - yc)) * 2;
    if(xa == mxx || xa == mnx || ya == mxy || ya == mny) rec1 = 0;
    if(xb == mxx || xb == mnx || yb == mxy || yb == mny) rec2 = 0;
    if(xc == mxx || xc == mnx || yc == mxy || yc == mny) rec3 = 0;
    return tot - tri1 - tri2 - tri3 - rec1 - rec2 - rec3;
}

公式法及代码剩余部分：

#include<bits/stdc++.h>
using namespace std;
int s(int xa, int ya, int xb, int yb, int xc, int yc) {
    return abs((xb - xa) * (yc - ya) - (xc - xa) * (yb - ya));
}
int main() {
    int xa, ya, xb, yb, xc, yc, xd, yd;
    cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
    int tri1 = s(xa, ya, xb, yb, xc, yc);
    int tri2 = s(xa, ya, xb, yb, xd, yd);
    int tri3 = s(xa, ya, xc, yc, xd, yd);
    int tri4 = s(xb, yb, xc, yc, xd, yd);
    if(tri1 + tri2 + tri3 == tri4) {
        cout << "No";
        return 0;
    }
    if(tri1 + tri2 + tri4 == tri3) {
        cout << "No";
        return 0;
    }
    if(tri1 + tri3 + tri4 == tri2) {
        cout << "No";
        return 0;
    }
    if(tri2 + tri3 + tri4 == tri1) {
        cout << "No";
        return 0;
    }
    cout << "Yes";
    return 0;
}