hdu 1542&poj 1151 Atlantis線分ツリー走査線矩形面積を求め

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1542
題意:n個の矩形を与えて、矩形の面積を求めてそして.
考え方:古典的な走査線法で矩形面積を求めます.座標が大きいため、横座標を離散化するか、縦座標を離散化するかを選択できます.
横座標を離散化すると、各長方形の上下2つの線分の左の始点、右の始点と高さ、および上または下のエッジが記録されます.
下から上へスキャンを選択すると、矩形の下辺を1に記録し、矩形の上辺を-1に記録します.
これらのセグメントを高さhで小さいものから大きいものに並べ替え、下から上へ走査し、毎回直線に遭遇し、下の場合、セグメントツリーの対応する区間+1になる.
上の場合、セグメントツリーの対応する区間-1です.次に、全区間が上書きされた長さを更新し、その長さ*(現在走査されている直線と次の直線の高さ差)を毎回加算します.
図を描くとはっきりします.

  1 #include 
  2 using namespace std;
  3 int n;
  4 #define maxn 210
  5 #define lson l, m, rt<<1
  6 #define rson m+1, r, rt<<1|1
  7 struct Line
  8 {
  9     double l, r, h;
 10     int mark;
 11 }line[maxn];
 12 double a[maxn], b[maxn];
 13 map <int, double> mp;
 14 int cnt;
 15 bool cmp(Line l1, Line l2)
 16 {
 17     return l1.h < l2.h;
 18 }
 19 int sum[maxn<<2];
 20 double cover[maxn<<2];
 21 void pushup(int l, int r, int rt)
 22 {
 23     if(sum[rt]) cover[rt] = mp[r+1] - mp[l];
 24     else
 25     {
 26         if(r == l) cover[rt] = 0;
 27         else cover[rt] = cover[rt<<1] + cover[rt<<1|1];
 28     }
 29 }
 30 void build(int l, int r, int rt)
 31 {
 32     cover[rt] = 0; sum[rt] = 0;
 33     if(l == r) return;
 34     int m = (l+r)>>1;
 35     build(lson);
 36     build(rson);
 37     pushup(l, r, rt);
 38 }
 39 void update(int L, int R, int val, int l, int r, int rt)
 40 {
 41     if(L == l && R == r)
 42     {
 43         sum[rt] += val;
 44         pushup(l, r, rt);
 45         return;
 46     }
 47     int m = (l+r)>>1;
 48     if(R <= m) update(L, R, val, lson);
 49     else if(L > m) update(L, R, val, rson);
 50     else
 51     {
 52         update(L, m, val, lson);
 53         update(m+1, R, val, rson);
 54     }
 55     pushup(l, r, rt);
 56 }
 57 int main() 
 58 {
 59     //freopen("in.txt", "r", stdin);
 60     //freopen("out.txt", "w", stdout);
 61     int cast = 0;
 62     while(~scanf("%d", &n) && n)
 63     {
 64         cnt = 0; mp.clear();
 65         for(int i = 1; i <= n; i++)
 66         {
 67             double x1, y1, x2, y2;
 68             scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
 69             a[cnt++] = x1; a[cnt++] = x2;
 70             
 71             line[i*2-1].l = x1; line[i*2-1].r = x2;    //  
 72             line[i*2-1].h = y1; line[i*2-1].mark = 1; 
 73             
 74             line[i*2].l = x1; line[i*2].r = x2;
 75             line[i*2].h = y2; line[i*2].mark = -1;     //  
 76         }
 77         for(int i = 0; i < cnt; i++) b[i] = a[i];
 78         sort(a, a+cnt);
 79         int precnt = cnt;
 80         cnt = unique(a, a+cnt) - a;
 81         
 82         for(int i = 0; i < precnt; i++)
 83         {
 84             mp[lower_bound(a, a+cnt, b[i]) - a + 1] = b[i];
 85         }
 86         sort(line+1, line+1+2*n, cmp);
 87         
 88         build(1, cnt, 1);
 89         double ans = 0;
 90         for(int i = 1; i <= 2*n; i++)
 91         {
 92             int ll = lower_bound(a, a+cnt, line[i].l) - a + 1;
 93             int rr = lower_bound(a, a+cnt, line[i].r) - a + 1;
 94             update(ll, rr-1, line[i].mark, 1, cnt, 1); 
 95             if(i != 2*n) ans += cover[1]*(line[i+1].h - line[i].h); 
 96         }
 97         cast++; printf("Test case #%d
", cast);
 98         printf("Total explored area: %.2f

", ans);
 99         
100     }
101     return 0;
102 }

 
転載先:https://www.cnblogs.com/titicia/p/5528544.html