首页 > 代码库 > FZU Problem 2148 Moon Game (判断凸四边形)
FZU Problem 2148 Moon Game (判断凸四边形)
题目链接
题意 : 给你n个点,判断能形成多少个凸四边形。
思路 :如果形成凹四边形的话,说明一个点在另外三个点连成的三角形内部,这样,只要判断这个内部的点与另外三个点中每两个点相连组成的三个三角形的面积和要与另外三个点组成的三角形面积相同。
中途忘了加fabs还错了好几次
1 //FZU2148 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <cmath> 6 #define eps 1e-9 7 #define zero(x) (((x)>0? (x) : (-x)) < eps ) 8 9 using namespace std ;10 11 struct point{double x;double y ;}p[32];12 struct Line{point a;point b;};13 14 double area(point a,point b,point c)15 {16 return a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - a.x * c.y - b.x * a.y ;17 }18 bool judge(point a,point b,point c,point d)19 {20 double sum = fabs(area(a,b,c))+fabs(area(a,b,d))+fabs(area(a,c,d)) ;21 double sun = fabs(area(b,c,d)) ;22 if(fabs(sum-sun) <eps) return true ;23 return false ;24 }25 bool solve(point a,point b,point c,point d)26 {27 if(judge(a,b,c,d) || judge(b,a,c,d) || judge(c,b,a,d) || judge(d,b,c,a)) return false ;28 return true ;29 }30 int main()31 {32 int T,casee = 1, n;33 scanf("%d",&T) ;34 while(T--)35 {36 scanf("%d",&n) ;37 for(int i = 0 ; i < n ; i++)38 scanf("%lf %lf",&p[i].x,&p[i].y) ;39 int ans = 0 ;40 for(int i = 0 ; i < n ; i++)41 {42 for(int j = i+1 ; j < n ; j++)43 {44 for(int k = j + 1 ; k < n ; k++)45 {46 for(int h = k+1 ; h < n ; h++)47 {48 if(solve(p[i],p[j],p[k],p[h])) ans ++ ;49 }50 }51 }52 }53 printf("Case %d: %d\n",casee ++ ,ans) ;54 }55 return 0 ;56 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。