首页 > 代码库 > FZU Problem 2148 Moon Game （判断凸四边形）

FZU Problem 2148 Moon Game （判断凸四边形）

2024-07-17 13:18:19   229人阅读

题目链接

题意 ： 给你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 }
View Code

 


联系
我们