Atlantis （POJ - 1151，扫描线模板）-白红宇的个人博客

Atlantis （POJ - 1151，扫描线模板）

发布日期：2021-05-04 06:49:42 浏览次数：39 分类：精选文章

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

一.题目链接：

二.题目大意：

求 n 个矩形的面积并.

三.分析：

模板题.

四.代码实现：

① O(N^2)

#include 
   
    #include 
    #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define eps 1e-6#define lc k * 2#define rc k * 2 + 1#define pi acos(-1.0)#define ll long long#define ull unsigned long longusing namespace std;const int M = (int)1e2;const int mod = 998244353;const ll inf = 0x3f3f3f3f3f3f3f3f;int n, ylen;double y[M * 2 + 5];int cnt[M * 2 + 5];map 
                 
                   row;struct node{ double x, y1, y2; int k;}line[M * 2 + 5];bool cmp(node a, node b){ return a.x < b.x;}double ScanLine(){ sort(y + 1, y + ylen + 1); ylen = unique(y + 1, y + ylen + 1) - (y + 1); for(int i = 1; i <= ylen; ++i) row[y[i]] = i; memset(cnt, 0, sizeof(cnt)); sort(line + 1, line + 2 * n + 1, cmp); double ans = 0.0; for(int i = 1; i <= 2 * n; ++i) { double y1 = line[i].y1, y2 = line[i].y2; for(int j = row[y1]; j < row[y2]; ++j) cnt[j] += line[i].k; double height = 0.0; for(int j = 1; j < ylen; ++j) { if(cnt[j]) height += y[j + 1] - y[j]; } ans += height * (line[i + 1].x - line[i].x); } return ans;}int main(){ int ca = 0; while(~scanf("%d", &n) && n) { ylen = 0; for(int i = 1; i <= n; ++i) { scanf("%lf %lf %lf %lf", &line[i * 2 - 1].x, &line[i * 2 - 1].y1, &line[i * 2].x, &line[i * 2].y2); line[i * 2 - 1].y2 = line[i * 2].y2, line[i * 2 - 1].k = 1; line[i * 2].y1 = line[i * 2 - 1].y1, line[i * 2].k = -1; y[++ylen] = line[i * 2 - 1].y1, y[++ylen] = line[i * 2 - 1].y2; } double ans = ScanLine(); printf("Test case #%d\n", ++ca); printf("Total explored area: %.2f\n\n", ans); } return 0;}

② O(N logN)

#include 
   
    #include 
    #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #define eps 1e-6#define lc k * 2#define rc k * 2 + 1#define pi acos(-1.0)#define ll long long#define ull unsigned long longusing namespace std;const int M = (int)1e2;const int mod = 998244353;const ll inf = 0x3f3f3f3f3f3f3f3f;int n, ylen;double y[M * 2 + 5];map 
                 
                   row;int cnt[M * 2 + 5];struct node{ double x, y1, y2; int k;}line[M * 2 + 5];bool cmp(node a, node b){ return a.x < b.x;}double ScanLine(){ sort(y + 1, y + ylen + 1); ylen = unique(y + 1, y + ylen + 1) - (y + 1); memset(cnt, 0, sizeof(cnt)); for(int i = 1; i <= ylen; ++i) row[y[i]] = i; sort(line + 1, line + 2 * n + 1, cmp); double ans = 0.0; for(int i = 1; i <= 2 * n; ++i) { double y1 = line[i].y1, y2 = line[i].y2; for(int j = row[y1]; j < row[y2]; ++j) cnt[j] += line[i].k; double height = 0.0; for(int j = 1; j < ylen; ++j) { if(cnt[j]) height += y[j + 1] - y[j]; } ans += height * (line[i + 1].x - line[i].x); } return ans;}int main(){ int ca = 0; while(~scanf("%d", &n) && n) { ylen = 0; for(int i = 1; i <= n; ++i) { scanf("%lf %lf %lf %lf", &line[i * 2 - 1].x, &line[i * 2 - 1].y1, &line[i * 2].x, &line[i * 2].y2); line[i * 2 - 1].y2 = line[i * 2].y2, line[i * 2 - 1].k = 1; line[i * 2].y1 = line[i * 2 - 1].y1, line[i * 2].k = -1; y[++ylen] = line[i * 2].y1, y[++ylen] = line[i * 2].y2; } printf("Test case #%d\n", ++ca); printf("Total explored area: %.2f\n\n", ScanLine()); } return 0;}

上一篇：Distance in Tree （CodeForces - 161D，点分治）

下一篇：Interval GCD（算法竞赛进阶指南，拓展更相减损之术 + 差分数组 + 线段树）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！