AT_abc266_c 题解

ikunTLE · 2024-11-25 21:19:43 · 题解

题目传送门

思路

对于任意一个凸多边形，它的每一个角都是 <180\degree 的。求四边形是否满足这个条件，可以求出 4 个点所构成的 4 条边的叉积，如果 4 个叉积符号相同，说明它们是顺时针或逆时针排列的，可以构成一个凸四边形。

AC CODE

#include<bits/stdc++.h>
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
struct node{
    int x,y;
}p1,p2,p3,p4;
int vector(node x1,node x2,node x3){
    return (x2.x-x1.x)*(x3.y-x2.y)-(x2.y-x1.y)*(x3.x-x2.x);
}
int main(){
    p1={read(),read()},p2={read(),read()},p3={read(),read()},p4={read(),read()};
    int l1=vector(p1,p2,p3),l2=vector(p2,p3,p4),l3=vector(p3,p4,p1),l4=vector(p4,p1,p2);
    printf(l1>0&&l2>0&&l3>0&&l4>0||l1<0&&l2<0&&l3<0&&l4<0?"Yes\n":"No\n");
    return 0;
}