L3-006 迎风一刀斩 (30 分)-PAT 团体程序设计天梯赛 GPLT

迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？

注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。

这里假设原始大旗的四边都与坐标轴是平行的。

输入格式：

输入第一行给出一个正整数N（≤20），随后给出N对多边形。每个多边形按下列格式给出：

kx1y1⋯xkyk

其中k（2<k≤10）是多边形顶点个数；(xi,yi)（0≤xi,yi≤108）是顶点坐标，按照顺时针或逆时针的顺序给出。

注意：题目保证没有多余顶点。即每个多边形的顶点都是不重复的，任意3个相邻顶点不共线。

输出格式：

对每一对多边形，输出YES或者NO。

输入样例：

8
3 0 0 1 0 1 1
3 0 0 1 1 0 1
3 0 0 1 0 1 1
3 0 0 1 1 0 2
4 0 4 1 4 1 0 0 0
4 4 0 4 1 0 1 0 0
3 0 0 1 1 0 1
4 2 3 1 4 1 7 2 7
5 10 10 10 12 12 12 14 11 14 10
3 28 35 29 35 29 37
3 7 9 8 11 8 9
5 87 26 92 26 92 23 90 22 87 22
5 0 0 2 0 1 1 1 2 0 2
4 0 0 1 1 2 1 2 0
4 0 0 0 1 1 1 2 0
4 0 0 0 1 1 1 2 0

输出样例：

YES
NO
YES
YES
YES
YES
NO
YES

分析：要让两个图形能够拼接成矩形只有四种情况 1.两个直角三角形 2.两个矩形 3.一个三角形配一个五角形 4.两个直角梯形。由于题目特殊的旋转限制，直角边只会和x轴或y轴平行。非矩形情况首先判断是不是有边数 – 1 的直角边，然后判断两个图形斜边是否相等。四边形则先判断是否是两个直角梯形，是的话高且斜边都相等则符合，如果是两个矩形任意一边相等即可。k1表示第一个图形的斜率，k2表示第二个图形的斜率，SLength中储存较短的平行于x轴的边，LLength中储存较长的平行于x轴的边，SWidth中储存较短的平行于y轴的边，LWidth中储存较长的平行于y轴的边，res表示有多少条直角边，dif为两点距离～

#include <bits/stdc++.h>
using namespace std;
int n, k1, k2, SLength, LLength, SWidth, LWidth, res, dif, D1, D2, a, b;
vector<pair<int, int>> A(10), B(10);
void deal(const vector<pair<int, int>> &C, const int &l) {
    res = SLength = LLength = SWidth = LWidth = 0;
    for (int i = 0; i < l; i++) {
        if (C[i].first == C[(i + 1) % l].first) {
            res++;
            dif = abs(C[i].second - C[(i + 1) % l].second);
            if (dif > LLength) SLength = LLength, LLength = dif;
            else SLength = dif;
        } else if (C[i].second == C[(i + 1) % l].second) {
            res++;
            dif = abs(C[i].first - C[(i + 1) % l].first);
            if (dif > LWidth) SWidth = LWidth, LWidth = dif;
            else SWidth = dif;
        }
    }
}
string judge() {
    if (k1 > 5 || k2 > 5) return "NO";
    if (k1 == 4 && k2 == 4) {
        deal(A, k1);
        if (res == 4) {
            D1 = LLength, D2 = LWidth;
            deal(B, k2);
            if (res != 4) return "NO";
            if (D1 == LLength || D2 == LWidth || D2 == LLength || D1 == LWidth) return "YES";
        } else if (res == 3) {
            if (SWidth == 0) D1 = LWidth, D2 = LLength - SLength;
            else  D1 = LLength, D2 = LWidth - SWidth;
            deal(B, k2);
            if (res != 3) return "NO";
            if (SWidth == 0 && D1 == LWidth && D2 == LLength - SLength) return "YES";
            else if (SLength == 0 && D1 == LLength && D2 == LWidth - SWidth) return "YES";

        }
        return "NO";
    }
    if (k2 > k1) swap(k1, k2), swap(A, B);
    deal(A, k1);
    if (res != k1 - 1) return "NO";
    D1 = LLength - SLength, D2 = LWidth - SWidth;
    deal(B, k2);
    if (res != k2 - 1) return "NO";
    if ((D1 == LLength  && D2 == LWidth) || (D2 == LLength && D1 == LWidth)) return "YES";
    return "NO";
}
int main() {
    cin >> n;
    while (n--) {
        cin >> k1;
        for (int i = 0; i < k1; i++) cin >> A[i].first >> A[i].second;
        cin >> k2;
        for (int i = 0; i < k2; i++) cin >> B[i].first >> B[i].second;
        cout << judge() << '\n';
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int n, k1, k2, SLength, LLength, SWidth, LWidth, res, dif, D1, D2, a, b;

vector<pair<int, int>> A(10), B(10);

void deal(const vector<pair<int, int>> &C, const int &l) {

res = SLength = LLength = SWidth = LWidth = 0;

for (int i = 0; i < l; i++) {

if (C[i].first == C[(i + 1) % l].first) {

res++;

dif = abs(C[i].second - C[(i + 1) % l].second);

if (dif > LLength) SLength = LLength, LLength = dif;

else SLength = dif;

} else if (C[i].second == C[(i + 1) % l].second) {

res++;

dif = abs(C[i].first - C[(i + 1) % l].first);

if (dif > LWidth) SWidth = LWidth, LWidth = dif;

else SWidth = dif;

}

string judge() {

if (k1 > 5 || k2 > 5) return "NO";

if (k1 == 4 && k2 == 4) {

deal(A, k1);

if (res == 4) {

D1 = LLength, D2 = LWidth;

deal(B, k2);

if (res != 4) return "NO";

if (D1 == LLength || D2 == LWidth || D2 == LLength || D1 == LWidth) return "YES";

} else if (res == 3) {

if (SWidth == 0) D1 = LWidth, D2 = LLength - SLength;

else D1 = LLength, D2 = LWidth - SWidth;

deal(B, k2);

if (res != 3) return "NO";

if (SWidth == 0 && D1 == LWidth && D2 == LLength - SLength) return "YES";

else if (SLength == 0 && D1 == LLength && D2 == LWidth - SWidth) return "YES";

}

return "NO";

}

if (k2 > k1) swap(k1, k2), swap(A, B);

deal(A, k1);

if (res != k1 - 1) return "NO";

D1 = LLength - SLength, D2 = LWidth - SWidth;

deal(B, k2);

if (res != k2 - 1) return "NO";

if ((D1 == LLength && D2 == LWidth) || (D2 == LLength && D1 == LWidth)) return "YES";

return "NO";

}

int main() {

cin >> n;

while (n--) {

cin >> k1;

for (int i = 0; i < k1; i++) cin >> A[i].first >> A[i].second;

cin >> k2;

for (int i = 0; i < k2; i++) cin >> B[i].first >> B[i].second;

cout << judge() << '\n';

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版