NKLAND - Mảnh đất tổ tiên

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#define MAX   1111
const double PI=acos(-1.0);
const double INF=2e9;
struct point {
    double x,y;
    point(){}
    point(const double &_x,const double &_y) {
        x=_x;y=_y;
    }
    point rotate(const double &alpha) {
        return (point(x*cos(alpha)-y*sin(alpha),x*sin(alpha)+y*cos(alpha)));
    }
};
double min(const double &x,const double &y) {
    if (x<y) return (x); else return (y);
}
double max(const double &x,const double &y) {
    if (x>y) return (x); else return (y);
}
int m,n;
point a[MAX];
point b[MAX];
void init(void) {
    int i;
    scanf("%d",&m);
    for (i=1;i<=m;i=i+1) {
        scanf("%lf",&a[i].x);
        scanf("%lf",&a[i].y);
    }
    scanf("%d",&n);
    for (i=1;i<=n;i=i+1) {
        scanf("%lf",&b[i].x);
        scanf("%lf",&b[i].y);
    }
}
void check(void) {
    int i,j;
    double alpha;
    double mxa,mna,mxb,mnb;
    for (i=0;i<100;i=i+1) {
        alpha=i*PI/100.0;
        mxa=-INF;mna=INF;
        mxb=-INF;mnb=INF;
        for (j=1;j<=m;j=j+1) {
            mxa=max(mxa,a[j].rotate(alpha).x);
            mna=min(mna,a[j].rotate(alpha).x);
        }
        for (j=1;j<=n;j=j+1) {
            mxb=max(mxb,b[j].rotate(alpha).x);
            mnb=min(mnb,b[j].rotate(alpha).x);
        }
        if (mxa<mnb) {
            printf("NO\n");
            return;
        }
        if (mxb<mna) {
            printf("NO\n");
            return;
        }
    }
    printf("YES\n");
}
int main(void) {
    int t,c;
    scanf("%d",&t);
    for (c=1;c<=t;c=c+1) {
        init();
        check();
    }
    return 0;
}

Download