HDU 1255 覆盖的面积

Problem Description

给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.

Input

输入数据的第一行是一个正整数T(1<=T<=100),代表测试数据的数量.每个测试数据的第一行是一个正整数N(1<=N<=1000),代表矩形的数量,然后是N行数据,每一行包含四个浮点数,代表平面上的一个矩形的左上角坐标和右下角坐标,矩形的上下边和X轴平行,左右边和Y轴平行.坐标的范围从0到100000.

注意:本题的输入数据较多,推荐使用scanf读入数据.

Output

对于每组测试数据,请计算出被这些矩形覆盖过至少两次的区域的面积.结果保留两位小数.

Sample Input

2
5
1 1 4 2
1 3 3 7
2 1.5 5 4.5
3.5 1.25 7.5 4
6 3 10 7
3
0 0 1 1
1 0 2 1
2 0 3 1      

Sample Output

7.63
0.00      

#include<cstdio>
#include<cmath>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 400005;
int n, m, T;
double l, r, a[maxn], ans;
struct seg
{
  double h, l, r;
  int k;
  bool operator <(const seg&a)
  {
    return h < a.h;
  }
}p[maxn];

struct ST
{
  double dis[maxn][2];
  int sum[maxn];
  void build(int x, int l, int r)
  {
    sum[x] = dis[x][0] = dis[x][1] = 0;
    if (l == r) return;
    else
    {
      int mid = l + r >> 1;
      build(x + x, l, mid);
      build(x + x + 1, mid + 1, r);
    }
  }
  void insert(int x, int l, int r, int ll, int rr, int v)
  {
    if (ll <= l&&r <= rr)
    {
      if (v < 0 && sum[x] == 0) goto next;
      sum[x] += v;
      if (sum[x] == 0)
      {
        if (l == r) dis[x][1] = dis[x][0] = 0;
        else
        {
          dis[x][1] = dis[x + x][1] + dis[x + x + 1][1];
          dis[x][0] = dis[x + x][0] + dis[x + x + 1][0];
        }
      }
      else if (sum[x] == 1)
      {
        if (l == r) dis[x][1] = 0, dis[x][0] = a[r + 1] - a[l];
        else
        {
          dis[x][1] = dis[x + x][1] + dis[x + x + 1][1] + dis[x + x][0] + dis[x + x + 1][0];
          dis[x][0] = a[r + 1] - a[l] - dis[x][1];
        }
      }
      else dis[x][0] = 0, dis[x][1] = a[r + 1] - a[l];
    }
    else
    {
      next:
      int mid = l + r >> 1;
      if (sum[x])
      {
        insert(x + x, l, mid, l, r, sum[x]);
        insert(x + x + 1, mid + 1, r, l, r, sum[x]);
        sum[x] = 0;
      }
      if (ll <= mid) insert(x + x, l, mid, ll, rr, v);
      if (rr > mid) insert(x + x + 1, mid + 1, r, ll, rr, v);
      dis[x][1] = dis[x + x][1] + dis[x + x + 1][1];
      dis[x][0] = dis[x + x][0] + dis[x + x + 1][0];
    }
  }
}st;

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
      scanf("%lf%lf%lf%lf", &l, &p[i + i - 1].h, &r, &p[i + i].h);
      p[i + i - 1].l = p[i + i].l = a[i + i - 1] = l;
      p[i + i - 1].r = p[i + i].r = a[i + i] = r;
      p[i + i - 1].k = 1;      p[i + i].k = -1;
    }
    sort(a + 1, a + n + n + 1);
    m = unique(a + 1, a + n + n + 1) - a;
    sort(p + 1, p + n + n + 1);
    ans = 0;  st.build(1, 1, m - 2);
    for (int i = 1; i <= n + n; i++)
    {
      int u = lower_bound(a + 1, a + m, p[i].l) - a;
      int v = lower_bound(a + 1, a + m, p[i].r) - a;
      st.insert(1, 1, m - 2, u, v - 1, p[i].k);
      ans += (p[i + 1].h - p[i].h)*st.dis[1][1];
    }
    printf("%.2lf\n", ans);
  } 
  return 0;
}