FZU 2148 Moon Game 判断凸四边形的个数

题意：T组样例，每组给定N个点 求可以构成的凸四边形的个数
思路：暴力枚举4个点：对于每4个点， 看看构成的是不是凹四边形，对于凹四边形 看下图

假设凹进去的那个点是a 则 S△abc +S△abd +S△acd=S△bcd
所以显而易见！ 注意 凹进去的点不一定是a 也可能是b 是c 是d 所以需要判断四下（具体见代码），四个都不是凹 则是真凸

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
struct node{int x,y;
}p[35];
double area(node a,node b,node c)
{return fabs(1.0*((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)))/2.0;
}
bool check(node a,node b,node c,node d)
{if(fabs(area(b,c,d)-area(a,b,c)-area(a,c,d)-area(a,b,d))<1e-6)return 0;return 1;
}
int main()
{int t,i,j;cin>>t;for(int tt=1;tt<=t;tt++){int n;cin>>n;int cnt=0;for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y;for(int i=0;i<n-3;i++)for(int j=i+1;j<n-2;j++)for(int k=j+1;k<n-1;k++)for(int l=k+1;l<n;l++){if(check(p[i],p[j],p[k],p[l])&&check(p[j],p[i],p[k],p[l])&&check(p[k],p[j],p[i],p[l])&&check(p[l],p[j],p[k],p[i]))cnt++;}printf("Case %d: %d\n",tt,cnt);}return 0; 
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！