扫描线 + 线段树 ： 求矩形面积的并 ---- hnu : 12884 Area Coverage

Area Coverage

Time Limit: 10000ms, Special Time Limit:2500ms, Memory Limit:65536KB

Total submit users: 16, Accepted users: 12

Problem 12884 : No special judgement

Problem description

In this day and age, a lot of the spying on other countries is done with the use of satellites and drones equipped with cameras. All these photographs of various sizes and from various sources can be combined to give a picture of the country as a whole.
Given the photographs (that is to say, the rectangular area covered by each, since the contents of the photographs themselves are of course top-secret!), can you work out what the total area is of all that is photographed? Note that certain areas can appear on multiple photographs and should be counted only once.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:
 one line with an integer n (1<=n<=1000): the number of photographs.
 n lines with four space-separated integers x1, y1, x2 and y2 (0<=x1; y1; x2; y2<=1 000 000, x1 < x2 and y1 < y2): the coordinates of the southwest and northeast corner, respectively, of each photograph. The photographs are all rectangular in shape with their other corners at (x1; y2) and (x2; y1).
The coordinates correspond to a flat two-dimensional space (i.e. we assume the Earth to be flat).

Output

Per test case:
 one line with an integer: the total area of all that appears on the photographs.

Sample Input

2
3
0 6 20 16
14 0 24 10
50 50 60 60
2
0 0 20 10
10 4 14 8

Sample Output

376
200

Problem Source

BAPC preliminary 2013

---

Mean:

在二维平面中，给你一些矩形的左下坐标(x1,y1)和右上坐标(x2,y2)，让你求这些矩形面积的并。

 

analyse:

 

 我们在y轴方向上维护一棵线段树。该线段树的模型是区间覆盖，即应该对像某个区间有没有被覆盖这样的查询，以及添加覆盖和删除覆盖这样的操作---也就是将矩形的左右两边界看作对y轴的覆盖来处理。我们将所有矩形的左右边界按照x坐标升序排序。每个矩形的左边界执行对y轴的覆盖操作，右边界执行对x轴的删除覆盖操作。

每次插入一条线段的时候，我们判断cover值(覆盖的次数)，如果>0那么就算面积。

如图：

初始时每条线段的cover都为0；

线段1插入后，所对应的区间cover变为1，当第二条线段插入时，我们先判断一下该区间上的cover值，发现有一段cover是大于0的，所以就将对应的面积(蓝色部分)加入ans中，此时线段2下半部分的cover值变为2，上部分的cover值变为1，还要把线段1的上部分的x坐标更新为线段2的x值；

当第三条直线插入时，同样的道理，加入的是黄色部分的面积；第四条进入时，加入的是紫色部分的面积。

这样，我们只需要在插入前先计算面积，当所有线段插入结束，answer也就出来了。

所以我们的线段树只需要两个函数:build和insert函数。

Time complexity：O(n*logn)

Source code：

/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-23-20.40
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define  LL long long
#define  ULL unsigned long long
using namespace std;

const int N = 1010;
double y[2 * N];
struct LINE
{
     double x, y_down, y_up;
     int flag;//左线段or右线段
};
LINE line[N << 1];
struct Tree
{
     int x;
     int cover;        // 覆盖次数
     bool flag;         // 是否为叶子节点
     int y_up, y_down;
};
Tree tree[( 1010 << 2 ) * 4];
bool cmp( LINE a, LINE b )
{
     return a.x < b.x;
}
void build( int l, int r, int x )
{
     tree[x].x = -1; //-1表示该区间没有线段
     tree[x].cover = 0;
     tree[x].flag = false;
     tree[x].y_up = y[r];
     tree[x].y_down = y[l];
     if( l + 1 == r ) // 叶子结点： (1,2) (2,3) (3,4) (4,5)....
     {
           tree[x].flag = true;
           return;
     }
     int tmp = x << 1;
     int mid = ( l + r ) >> 1;
     build( l, mid, tmp );
     build( mid, r, tmp + 1 );;
}
double insert( int i, double x, double l, double r, int flag )
{
     if( r <= tree[i].y_down || l >= tree[i].y_up ) //要插入的线段不在该区间
           return 0;
     if( tree[i].flag ) //叶子节点
     {
           if( tree[i].cover > 0 )     // 需要求并面积
           {
                 double temp_x = tree[i].x;
                 double ans = ( x - temp_x ) * ( tree[i].y_up - tree[i].y_down ); // 宽*高
                 tree[i].x = x; // 更新树中的x值
                 tree[i].cover += flag;
                 return ans;
           }
           else
           {
                 tree[i].cover += flag;
                 tree[i].x = x;
                 return 0;
           }
     }
     double ans1, ans2;
     int tmp = i << 1;
     ans1 = insert( tmp, x, l, r, flag );
     ans2 = insert( tmp + 1, x, l, r, flag );
     return ans1 + ans2;
}

int main()
{
     ios_base::sync_with_stdio( false );
     cin.tie( 0 );
     int T;
     cin >> T;
     double x1, y1, x2, y2;
     while( T-- )
     {
           int n;
           cin >> n;
           int index = 1;
           for( int i = 1; i <= n; i++ )
           {
                 scanf( "%lf %lf %lf %lf", &x1, &y1, &x2, &y2 );
                 y[index] = y1;
                 line[index].x = x1;
                 line[index].y_down = y1;
                 line[index].y_up = y2;
                 line[index].flag = 1;
                 index++;
                 y[index] = y2;
                 line[index].x = x2;
                 line[index].y_down = y1;
                 line[index].y_up = y2;
                 line[index].flag = -1;
                 index++;
           }
           index--;
           double ans = 0.0;
           sort( line + 1, line + 1 + index, cmp );
           sort( y + 1, y + 1 + index );
           build( 1, index, 1 );
           for( int i = 1; i <= index; i++ )
           {
                 ans += insert( 1, line[i].x, line[i].y_down, line[i].y_up, line[i].flag );
           }
           printf( "%.0lf ", ans );
     }
     return 0;
}