简单几何(判断矩形的位置) UVALive 7070 The E-pang Palace(14广州B)-白红宇

简单几何(判断矩形的位置) UVALive 7070 The E-pang Palace(14广州B)

阅读量：5797 次

发布时间：2019-06-18

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

题意：给了一些点，问组成两个不相交的矩形的面积和最大

分析：暴力枚举，先找出可以组成矩形的两点并保存起来(vis数组很好)，然后写个函数判断四个点是否在另一个矩形内部。当时没有保存矩形，用for来找矩形，结果写糊涂了忘记判断回形的情况。。。

/************************************************* Author        :Running_Time* Created Time  :2015/11/6 星期五 17:00:44* File Name     :B_2.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 = 2e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-10;const double PI = acos (-1.0);struct Point { int x, y; Point () {} Point (int x, int y) : x (x), y (y) {} bool operator < (const Point &r) const { if (x == r.x) return y < r.y; else return x < r.x; }}p[33];struct Matrix { Point a, b; Matrix () {} Matrix (Point a, Point b) : a (a), b (b) {}};vector
                      
                        mat;bool vis[N][N];int inside(Point p, Point a, Point b) { if (p.x >= a.x && p.x <= b.x && p.y <= a.y && p.y >= b.y) { if (p.x > a.x && p.x < b.x && p.y < a.y && p.y > b.y) return -1; else return 1; } else return 0;}int area_mat(int i) { return (mat[i].b.x - mat[i].a.x) * (mat[i].a.y - mat[i].b.y);}int judge(int i, int j) { Point ic = Point (mat[i].a.x, mat[i].b.y), id = Point (mat[i].b.x, mat[i].a.y); int res1 = inside (mat[i].a, mat[j].a, mat[j].b); int res2 = inside (mat[i].b, mat[j].a, mat[j].b); int res3 = inside (ic, mat[j].a, mat[j].b); int res4 = inside (id, mat[j].a, mat[j].b); if (!res1 && !res2 && !res3 && !res4) return 0; else if (res1 == -1 && res2 == -1 && res3 == -1 && res4 == -1) return -1; else return 1;}int main(void) { int n; while (scanf ("%d", &n) == 1) { if (!n) break; mat.clear (); memset (vis, false, sizeof (vis)); for (int i=0; i
                       
                        = x2 || y1 <= y2) continue; if (!vis[x1][y2] || !vis[x2][y1]) continue; mat.push_back (Matrix (Point (x1, y1), Point (x2, y2))); } } int ans = 0; for (int i=0; i

这个很挫的代码放在这留个念。。。

/************************************************* Author        :Running_Time* Created Time  :2015/10/14 星期三 14:59:33* File Name     :B.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;const int N = 33;const int M = 210;const int INF = 0x3f3f3f3f;struct Point { int x, y; bool operator < (const Point &r) const { if (x == r.x) return y < r.y; else return x < r.x; }}p[N];vector
                      
                        vx[M], vy[M];int cal(int la, int lb) { if (la < 0) la = -la; if (lb < 0) lb = -lb; return la * lb;}int main(void) { int n; while (scanf ("%d", &n) == 1) { if (!n) break; for (int i=0; i<=200; ++i) { vx[i].clear (); vy[i].clear (); } for (int i=1; i<=n; ++i) { scanf ("%d%d", &p[i].x, &p[i].y); } sort (p+1, p+1+n); for (int i=1; i<=n; ++i) { vx[p[i].x].push_back (i); vy[p[i].y].push_back (i); } int ans = 0; bool flag = false; for (int i=1; i<=n; ++i) { //i one int x = p[i].x, y = p[i].y; if (vx[x].size () <= 1 || vy[y].size () <= 1) continue; for (int j=0; j
                       
                        = 4) { for (int r=0; r
                        
                         = 4) { for (int r=0; r
                         
                           jjy) swap (yy, jjy); if (y <= yy && yy <= jy) continue; if (y <= jjy && jjy <= jy) continue; if (vy[yy].size () <= 1 || vy[jjy].size () <= 1) continue; for (int o=0; o

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

你可能感兴趣的文章