HDU-1255 覆盖的面积矩形面积交-白红宇

HDU-1255 覆盖的面积矩形面积交

阅读量：6575 次

发布时间：2019-06-24

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

题义为给定N个矩形，求其重叠的图形面积，该题采用线段树离散化y轴坐标，并且采用分割思想，只依据x坐标来进行分割。

我们将N个矩形化为N*2条线段来处理，该结构体中的成员变量为 x, yl, yh, 分别是x轴坐标，相对高低的y轴坐标，即线段的两个端点值。

1.将所有的线段排一次序，并将y轴所有坐标轴点排序并进行离散化；

2.在从左往右扫描每一条线段时，我们应该理解为此时我们将把该线段的右边区域认定为全部被覆盖；

3.查找该x轴坐标下被覆盖的y轴坐标的次数，因为一旦y轴被覆盖，则说明其右边无限长的区域被覆盖，如果得到 [y1,y2] 这段区间被覆盖了，那么该点到下一个相邻的x轴的坐标之间

的区域一定是被覆盖的，那么只要这段区间被覆盖2次或以上，这部分的面积就能够求出来了。

代码如下：

#include 
     
       #include 
      
        #include 
       
         #include 
         #include 
         
           #define MAXN 2005 using namespace std; struct Node {
   double x, yl, yh; int lr; bool operator < (Node t) const     {
   return x < t.x;     } }e[MAXN]; struct {
   int l, r, cover; }seg[3*MAXN]; double yy[MAXN]; void creat(int f, int l, int r) {
   int mid = (l+r)>>1;     seg[f].l = l, seg[f].r = r;     seg[f].cover = 0; if (r - l > 1)     {
           creat(f<<1, l, mid);         creat(f<<1|1, mid, r);     } } void modify(int f, int l, int r, int val) {
   int mid = (seg[f].l + seg[f].r)>>1; if (seg[f].l == l && seg[f].r == r)     {
           seg[f].cover += val;     } else if (seg[f].r - seg[f].l > 1)     {
   if (l >= mid)             modify(f<<1|1, l, r, val); else if (r <= mid)             modify(f<<1, l, r, val); else         {
               modify(f<<1, l, mid, val);             modify(f<<1|1, mid, r, val);         }     } } void query(int f, double &ans) {
   if (seg[f].cover > 1)     {
           ans += yy[seg[f].r]-yy[seg[f].l]; //   printf("ans = %lf\n", ans);     } else if (seg[f].r - seg[f].l > 1)     {
   //    if (seg[f].cover != 0) //    {
                seg[f<<1].cover += seg[f].cover;             seg[f<<1|1].cover += seg[f].cover; //    seg[f].cover = 0; //    } // lazy思想处理的话，该题时间上开销要大很多（往下传递过多），所以采用回溯相对较好         query(f<<1, ans);         query(f<<1|1, ans);         seg[f<<1].cover -= seg[f].cover;         seg[f<<1|1].cover -= seg[f].cover;     } } int main() {
   int T, N; double x1, x2, y1, y2, ans, res;     scanf("%d", &T); while (T--)     {
           res = 0;         map
          
           mp; scanf("%d", &N); for (int i = 1, j = 1; i <= N; ++i, j+=2) { scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); e[j].x = x1, e[j].yl = y1, e[j].yh = y2; e[j].lr = 1; e[j+1].x = x2, e[j+1].yl = y1, e[j+1].yh = y2; e[j+1].lr = -1; yy[j] = y1, yy[j+1] = y2; } sort(e+1, e+1+2*N); sort(yy+1, yy+1+2*N); int cnt = unique(yy+1, yy+1+2*N) - (yy+1); creat(1, 1, cnt); for (int i = 1; i <= cnt; ++i) mp[yy[i]] = i; for (int i = 1; i < 2*N; ++i) { ans = 0; modify(1, mp[e[i].yl], mp[e[i].yh], e[i].lr); query(1, ans); res += ans * (e[i+1].x - e[i].x); } printf("%.2lf\n", res); } return 0; }

转载地址：http://mvgjo.baihongyu.com/

你可能感兴趣的文章