暴力(判凸四边形) FZOJ 2148 Moon Game-白红宇

暴力(判凸四边形) FZOJ 2148 Moon Game

阅读量：6240 次

发布时间：2019-06-22

本文共 1970 字，大约阅读时间需要 6 分钟。

题意：给了n个点的坐标，问能有几个

分析：数据规模小，直接暴力枚举，每次四个点判断是否会是凹四边形，条件是有一个点在另外三个点的内部，那么问题转换成判断一个点d是否在三角形abc内

　　　　易得S (abd) + S (acd) + S (bcd) == S (abc)，求三角形面积

收获：比赛时没写出来，没想到用面积就轻松搞定，脑子有点乱，开始敲了计算几何点是否在凸多边形内的模板，WA了，整个人都不好了。收获就是要把计算几何的基础补上来

代码：

/************************************************* Author        :Running_Time* Created Time  :2015-8-23 13:40:19* File Name     :H.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 33;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;const double PI = acos (-1.0);struct Point { double x, y;};int n;Point pp[N];double area(Point a, Point b, Point c) { return fabs (0.5 * (a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - a.x * c.y - b.x * a.y));}bool cal(Point a, Point b, Point c, Point d) { double sum = area (a, b, d) + area (a, c, d) + area (b, c, d); double tot = area (a, b, c); if (fabs (sum - tot) < EPS) return false; return true;}bool judge(Point a, Point b, Point c, Point d) { if (!cal (a, b, c, d)) return false; if (!cal (a, b, d, c)) return false; if (!cal (a, d, c, b)) return false; if (!cal (d, b, c, a)) return false; return true;}int work(void) { int ret = 0; for (int i=1; i<=n; ++i) { for (int j=i+1; j<=n; ++j) { for (int k=j+1; k<=n; ++k) { for (int l=k+1; l<=n; ++l) { if (judge (pp[i], pp[j], pp[k], pp[l])) ret++; } } } } return ret;}int main(void) { int T, cas = 0; scanf ("%d", &T); while (T--) { scanf ("%d", &n); for (int i=1; i<=n; ++i) { scanf ("%lf%lf", &pp[i].x, &pp[i].y); } printf ("Case %d: %d\n", ++cas, work ()); } return 0;}

转载于:https://www.cnblogs.com/Running-Time/p/4753064.html

你可能感兴趣的文章