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;
}