简单几何(线段覆盖) POJ 3347 Kadj Squares-白红宇

简单几何(线段覆盖) POJ 3347 Kadj Squares

阅读量：4639 次

发布时间：2019-06-09

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

题意：告诉每个矩形的边长，它们是紧贴着的，问从上往下看，有几个还能看到。

分析：用网上猥琐的方法，将边长看成左端点到中心的距离，这样可以避免精度问题。然后先求出每个矩形的左右端点，然后如果被覆盖那么将端点更新到被覆盖的位置。最后看那些更新后左端点小于右端点，这些是可以看得到的。

/************************************************* Author        :Running_Time* Created Time  :2015/10/28 星期三 11:48:32* File Name     :POJ_3347.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 = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-10;const double PI = acos (-1.0);struct Square { int l, r, len;}s[55];int main(void) { int n; while (scanf ("%d", &n) == 1) { if (!n) break; for (int i=1; i<=n; ++i) { scanf ("%d", &s[i].len); s[i].l = 0; for (int j=1; j
                      
                        s[i].l) s[i].l = tmp; } s[i].r = s[i].l + s[i].len * 2; } for (int i=2; i<=n; ++i) { for (int j=1; j
                       
                         s[i].l) { s[j].r = s[i].l; } else if (s[j].len > s[i].len && s[j].r > s[i].l) { s[i].l = s[j].r; } } } for (int i=1; i<=n; ++i) { if (s[i].l < s[i].r) { printf ("%d ", i); } } puts (""); } //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;}

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

你可能感兴趣的文章

配置错误，无法识别的配置节 system.serviceModel 解决方案