poj 1151-白红宇

poj 1151

阅读量：5279 次

发布时间：2019-06-14

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

分类：线段树

题意：求矩阵面积并

输入：矩阵个数N，每个矩阵的左下角坐标和右上角坐标

输出：矩阵的面积并

很久没有做数据结构了，这道题算是比较经典，难度相对适中的吧，今天拿出来写了一遍。数据结构主要是线段树。虽然写过几次了，每次动手写都会遇到一些问题。做个笔记：

1.基本算法：

将矩形沿着Y方向的平行于X轴的线作为扫描线。核心算法在于对于n – 1条扫描线作的高度差用来算矩阵的面积

上面两张是比较好理解的图（来自网络）。线段树的作用就在于保存当前的X轴覆盖区域的长度为多少，每一次，顺着扫描方向，插入一段扫描线更新当前的覆盖区域长度（会有重合）。

一个技巧：把下边的边flag设置为true，上面的边设置为false，然后在线段树中记录有多少个覆盖记录，以方便计算

2.去重与排序

可以用STL的unique，当然也可以手写，排序也是不可缺少的，本题数据量而言，时间复杂度是完全可以满足的

3.二分查找

一种映射关系，因为x坐标是浮点数，所以不可以直接离散化，需要一种映射

4.树的写法

node需要携带什么信息？如何建树和存储？

重点中的重点：插入线段的时候应该如何处理？

如何更新？

1 #include 
     
        2 #include 
      
         3 #include 
         4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
               10 #include 
              
                11 #include 
               
                 12 #include 
                
                  13 #include 
                 
                   14 #include 
                  
                    15 #include 
                   
                     16 #include 
                    
                      17 #include 
                     
                       18 #include 
                      
                        19 #include 
                       
                         20 #include 
                        
                          21 using namespace std; 22 23 ///宏定义 24 const int INF = 990000000; 25 const int MAXN = 2000; 26 const int maxn = MAXN; 27 ///全局变量 和 函数 28 29 struct line 30 { 31 double ypos; 32 double xleftPos, xrightPos; 33 bool flag; 34 bool operator < (const line& l) 35 { 36 return ypos < l.ypos; 37 } 38 }; 39 40 struct node 41 { 42 int lchild, rchild; 43 int ll, rr; 44 double length; 45 int cover; 46 }; 47 double xpos[maxn]; 48 49 void buildTree(int left, int right, int cur, node* T) 50 { 51 T[cur].ll = left; 52 T[cur].rr = right; 53 T[cur].length = 0; 54 if (right - left == 1) 55 { 56 T[cur].lchild = T[cur].rchild = -1; 57 return; 58 } 59 T[cur].lchild = 2 * cur; 60 T[cur].rchild = 2 * cur + 1; 61 int mid = (left + right) / 2; 62 buildTree(left, mid, 2 * cur, T); 63 buildTree(mid, right, 2 * cur + 1, T); 64 } 65 node tree[maxn * 4]; 66 67 line lines[maxn]; 68 69 void update(node* T, int cur, bool flag) 70 { 71 if (T[cur].lchild == -1 && T[cur].rchild == -1) 72 { 73 int L = T[cur].ll; 74 int R = T[cur].rr; 75 if (flag) 76 { 77 T[cur].cover++; 78 if (T[cur].cover == 1) 79 { 80 T[cur].length += xpos[R - 1] - xpos[L - 1]; //注意xpos数组的下标 81 } 82 } 83 else if(!flag) 84 { 85 T[cur].cover--; 86 if (T[cur].cover == 0) 87 { 88 T[cur].length -= xpos[R - 1] - xpos[L - 1]; //注意xpos数组的下标 89 } 90 } 91 return; 92 } 93 else 94 T[cur].length = T[cur * 2].length + T[cur * 2 + 1].length; 95 } 96 void insert(node* T, int cur, int Left, int Right, bool flag) 97 { 98 if (T[cur].lchild == -1 && T[cur].rchild == -1) 99 {100 101 }102 else103 {104 int mid = (T[cur].ll + T[cur].rr) / 2;105 if (Right <= mid)106 { 107 insert(T, cur * 2, Left, Right, flag);108 }109 else if (Left >= mid)110 {111 insert(T, cur * 2 + 1, Left, Right, flag);112 }113 else114 {115 insert(T, cur * 2, Left, mid, flag);116 insert(T, cur * 2 + 1, mid, Right, flag);117 }118 }119 update(T, cur, flag);120 }121 122 int b_search(double *arr, int n, double val);123 int main()124 {125 ///变量定义126 int n;127 int cases = 1;128 while (scanf("%d", &n) && n != 0)129 {130 double area = 0;131 memset(tree, 0, sizeof(tree));132 int lineNum = 0;133 int xposNum = 0;134 for (int i = 0; i < n; i++)135 {136 double x1, y1, x2, y2;137 scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);138 lines[lineNum].ypos = y1;139 lines[lineNum].xleftPos = x1;140 lines[lineNum].xrightPos = x2;141 lines[lineNum].flag = true;142 lineNum++;143 144 lines[lineNum].ypos = y2;145 lines[lineNum].xleftPos = x1;146 lines[lineNum].xrightPos = x2;147 lines[lineNum].flag = false;148 lineNum++;149 150 xpos[xposNum++] = x1;151 xpos[xposNum++] = x2;152 }153 sort(lines, lines + lineNum);154 sort(xpos, xpos + xposNum);155 int k = 0;156 for (int i = 1; i < xposNum; i++)157 {158 if (xpos[i] != xpos[k])159 {160 xpos[++k] = xpos[i];161 }162 }163 xposNum = k + 1;164 sort(xpos, xpos + xposNum);165 166 //建立线段树167 buildTree(1, xposNum, 1, tree);168 169 for (int i = 0; i < lineNum - 1; i++)170 {171 //找到下标172 int ll = b_search(xpos, xposNum, lines[i].xleftPos);173 int rr = b_search(xpos, xposNum, lines[i].xrightPos);174 bool flag = lines[i].flag;175 //插入到线段树176 insert(tree, 1, ll + 1, rr + 1, flag); 177 178 //179 area += (lines[i + 1].ypos - lines[i].ypos) * tree[1].length;180 }181 printf("Test case #%d\n", cases++);182 printf("Total explored area: %.2f\n\n", area);183 }184 185 ///结束186 return 0;187 }188 189 int b_search(double *arr, int n, double val)190 {191 int low = 0;192 int high = n - 1;193 int mid;194 while (low <= high)195 {196 mid = (low + high) >> 1;197 if (arr[mid] == val)198 {199 return mid;200 }201 else if (arr[mid] > val)202 {203 high = mid - 1;204 }205 else206 {207 low = mid + 1;208 }209 }210 return -1;211 }

转载于:https://www.cnblogs.com/rayforsure/p/3323612.html

你可能感兴趣的文章