迎风一刀斩（几何）

程序员文章站 2022-05-12 12:01:28

...

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

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

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

输入格式：
输入第一行给出一个正整数N（≤20），随后给出N对多边形。每个多边形按下列格式给出：
…
其中k（2<k≤10）是多边形顶点个数；…是顶点坐标，按照顺时针或逆时针的顺序给出。

注意：题目保证没有多余顶点。即每个多边形的顶点都是不重复的，任意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

反思
写了两个小时，还是wa,我已哭晕在厕所里QAQ
全题没有啥技术含量，但是就是太考验耐心和细心了。总之一句话“be patient!!!”
https://blog.csdn.net/summonlight/article/details/62045520?utm_medium=distribute.pc_relevant.none-task-blog-title-3&spm=1001.2101.3001.4242
以下代码是错的，但思路明确，请勿复制粘贴（注：我已经懒得检查了）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Node{
    ll x,y;
};

void judge6(Node p1[],Node p2[]){
    ll ans1[3],ans2[3],j1=0,j2=0;
    for(int i = 0; i < 3; i++){
        int j = (i+1)%3;
            ans1[j1++] = (p1[i].x - p1[j].x)*(p1[i].x - p1[j].x) + (p1[i].y - p1[j].y)*(p1[i].y - p1[j].y);
            ans2[j2++] = (p2[i].x - p2[j].x)*(p2[i].x - p2[j].x) + (p2[i].y - p2[j].y)*(p2[i].y - p2[j].y);

    }
    sort(ans1,ans1+3);
    sort(ans2,ans2+3);
    for(int i = 0; i < 3; i++){
        //cout << ans1[i] << endl;
        //cout << ans2[i] << endl;
        if(ans1[i] != ans2[i]){
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

void judge7(Node p1[], Node p2[]){
    ll ans1[3],ans2[4],j1=0,j2=0;
    for(int i = 0; i < 3; i++){
        int j = (i+1)%3;
            ans1[j1++] = (p1[i].x - p1[j].x)*(p1[i].x - p1[j].x) + (p1[i].y - p1[j].y)*(p1[i].y - p1[j].y);
            //cout << ans1[j1-1] << endl;
    }

    for(int i = 0; i < 4; i++){
        int j = (i+1)%4;
            ans2[j2++] = (p2[i].x - p2[j].x)*(p2[i].x - p2[j].x) + (p2[i].y - p2[j].y)*(p2[i].y - p2[j].y);
            //cout << ans2[j2-1] << endl;

    }

    int t[20],cnt = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 4; j++){

            if(ans1[i] == ans2[j] && ans1[i] != 0){
                t[cnt++] = ans1[i]*2;
                ans1[i] = 0;
                ans2[j] = 0;

            }
        }
    }
    sort(ans1, ans1+3);
    sort(ans2, ans2+4);
    if(cnt < 2){
        cout << "NO" << endl;
        return;
    }
    if(cnt == 3){
        for(int i = 0; i < cnt; i++){
            if(ans2[3] == t[i]){
                cout << "YES" << endl;
                return;
            }
        }
        cout << "NO" << endl;
        return;
    }

    if(sqrt(ans2[3]) == sqrt(ans2[2]) + sqrt(ans1[2])){
        cout << "YES" << endl;
        return;
    }
    cout << "NO" << endl;

}

void judge81(Node p1[], Node p2[]){
    ll ans1[3],ans2[4],j1=0,j2=0;
    for(int i = 0; i < 4; i++){
            int j = (i+1)%4;
            ans1[j1++] = (p1[i].x - p1[j].x)*(p1[i].x - p1[j].x) + (p1[i].y - p1[j].y)*(p1[i].y - p1[j].y);
            ans2[j2++] = (p2[i].x - p2[j].x)*(p2[i].x - p2[j].x) + (p2[i].y - p2[j].y)*(p2[i].y - p2[j].y);
            //cout << ans2[j2-1] << endl;

    }

    int cnt = 0;
    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(ans1[i] == ans2[j]){
                ans1[i] = 0;
                ans2[i] = 0;
                cnt++;
            }
        }
    }
    if(cnt < 2){
        cout << "NO" << endl;
        return;
    }
    sort(ans1, ans1+4);
    sort(ans2, ans2+4);
    if(ans1[3]+ans2[2] == ans1[2]+ans2[3]){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }


}

void judge82(Node p1[], Node p2[]){
    ll ans1[3],ans2[5],j1=0,j2=0;
    for(int i = 0; i < 3; i++){
        for(int j = i+1; j < 3; j++){
            ans1[j1++] = (p1[i].x - p1[j].x)*(p1[i].x - p1[j].x) + (p1[i].y - p1[j].y)*(p1[i].y - p1[j].y);
            //cout << ans1[j1-1] << endl;
        }
    }
    for(int i = 0; i < 5; i++){
        int j = (i+1)%5;
            ans2[j2++] = (p2[i].x - p2[j].x)*(p2[i].x - p2[j].x) + (p2[i].y - p2[j].y)*(p2[i].y - p2[j].y);
            //cout << ans2[j2-1] << endl;

    }
    sort(ans1, ans1+3);
    sort(ans2, ans2+5);
    int cnt = 0;
    for(int i = 0; i < 5; i++){
            if(ans1[2] == ans2[i]){
                ans1[2] = 0;
                ans2[i] = 0;
                cnt++;
                break;
            }

    }
    if(cnt < 1){
        cout << "NO" << endl;
        return;
    }
    sort(ans1, ans1+3);
    sort(ans2, ans2+5);

    bool flag1 = false, flag2 = false;
    for(int i = 1; i < 5; i++){
        for(int j = 1; j < 5; j++){
            if(sqrt(ans2[i]) + sqrt(ans1[2]) == sqrt(ans2[j]) && i != j){
                ans2[i] = 0;
                ans1[2] = 0;
                ans2[j] = 0;
                flag1 = true;
                break;
        }


        }
    }
    sort(ans1, ans1+3);
    sort(ans2, ans2+5);
    if(sqrt(ans2[4]) == sqrt(ans1[2])+sqrt(ans2[3])){
        flag2 = true;
    }
    if(flag1 && flag2){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

}
int main(){
    int N;
    cin >> N;
    while(N--){
        //6~8个顶点
        int v1,v2;
        Node p1[20],p2[20];

        cin >> v1;
        for(int i = 0; i < v1; i++){
            cin >> p1[i].x >> p1[i].y;
        }
        cin >> v2;
        for(int i = 0; i < v2; i++){
            cin >> p2[i].x >> p2[i].y;
        }

        if(v1+v2 == 6){
            judge6(p1,p2);
        }else if(v1+v2 == 7){
            if(v1 == 3){
                judge7(p1,p2);
            }else{
                judge7(p2,p1);
            }

        }else if(v1+v2 == 8){
            if(v1 == 4 && v2 == 4){
                judge81(p1,p2);
            }else if(v1 == 3){
                judge82(p1,p2);
            }else if(v1 == 5){
                judge82(p2,p1);
            }

        }else{
            cout << "NO" << endl;
        }


    }
    return 0;
}

看了博主的不到100行简单代码，总结思路如下：
迎风一刀斩（几何）
思路基本类似，但是他的思路比较清晰：
check()可以通过引用返回横向的长(X)短(x)边，纵向的长(Y)短(y)边，以及平行坐标轴的边数(strt)。
penta()本来是用来判断五边形和三角形的，后来发现前三个写起来都一样就都合在一起了。
quaqua()用来判断两个四边形能不能拼成矩形，其中两个矩形是一种特殊情况，如果一个的边长是(A, B)，另一个是(X, Y)，只要A/B中的一个和X/Y中的一个相等就可以了。
其他一般的情况都是通过图中的相等关系判断的

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
PII a[6],b[6];

inline void input(PII a[],int &n)
{
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]=PII(x,y);
    }
}

inline void check(PII a[],int n,int &X,int &x,int &Y,int &y,int &strt)
{
    X=x=Y=y=strt=0;
    for (int i=0;i<n;i++) {
        if (a[i].first==a[(i+1)%n].first) {
            strt++;
            int tmp=abs(a[i].second-a[(i+1)%n].second);
            if (tmp>Y) y=Y,Y=tmp;
            else y=tmp;
        } else if (a[i].second==a[(i+1)%n].second) {
            strt++;
            int tmp=abs(a[i].first-a[(i+1)%n].first);
            if (tmp>X) x=X,X=tmp;
            else x=tmp;
        }
    }
}

inline bool penta(int n,int m)
{
    int x,X,y,Y,strt;
    check(b,m,X,x,Y,y,strt);
    if (strt!=m-1) return false;
    int A=Y-y,B=X-x;
    check(a,n,X,x,Y,y,strt);
    if (strt!=n-1) return false;
    return (X==A&&Y==B)||(X==B&&Y==A);
}

bool quaqua()
{
    int x,X,y,Y,strt;
    check(b,4,X,x,Y,y,strt);
    if (strt<3) return false;
    if (strt==4) {
        int A=X,B=Y;
        check(a,4,X,x,Y,y,strt);
        if (strt!=4) return false;
        return A==X||A==Y||B==X||B==Y;
    }
    int height,A,B;
    if (y==0) {
        height=Y;A=X;B=x;
    } else {
        height=X;A=Y;B=y;
    }
    check(a,4,X,x,Y,y,strt);
    if (strt<3) return false;
    if (y==0) {
        return height==Y&&x+A==X+B;
    } else {
        return height==X&&y+A==Y+B;
    }
}

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--) {
        input(a,n);
        input(b,m);
        if (n>m) {
            swap(n,m);
            swap(a,b);
        }
        bool f=false;
        if (n==4&&m==4) f=quaqua();
        else f=penta(n,m);
        puts(f?"YES":"NO");
    }
    return 0;
}

迎风一刀斩（几何）

几何画板怎么用线段标记三角形的边和角?

几何画板坐标系中怎么绘制函数表达式图?

七月，党旗迎风飘扬

PS制作对称的几何图案

cdr怎么画几何静物素描立体图形?

SolidWorks草图几何关系怎么添加?

AE怎么做动图?AE制作几何图形变换动画的教程

coreldraw怎么画正方体?CDR做素描几何体效果的方法

Android开发实现的几何图形工具类GeometryUtil完整实例

几何画板工具箱乱码怎么办几何画板工具箱乱码解决办法

迎风一刀斩（几何）

几何画板怎么用线段标记三角形的边和角?

几何画板坐标系中怎么绘制函数表达式图?

七月，党旗迎风飘扬

PS制作对称的几何图案

cdr怎么画几何静物素描立体图形?

SolidWorks草图几何关系怎么添加?

AE怎么做动图?AE制作几何图形变换动画的教程

coreldraw怎么画正方体?CDR做素描几何体效果的方法

Android开发实现的几何图形工具类GeometryUtil完整实例

几何画板工具箱乱码怎么办 几何画板工具箱乱码解决办法

几何画板工具箱乱码怎么办几何画板工具箱乱码解决办法