青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

算法學社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

題目描述:

    給出很多矩形,求矩形并的面積。

吐槽:

    1. 經過傻崽大神的教誨,我決定不再向以前那樣惡意縮短代碼了
    2. 看來.... 要慢慢改...
    3. 思路仍然是按照傻崽大神的blog寫的... 然后轉成了zkw版線段樹...

思路分析:

    離散化之后,在腦海中想像一個掃描線,按照y軸從小到大的順序掃過去。
    掃到的肯定是一個x軸的區間集合。 如果遇到了“新邊”就加到集合中,遇到“舊邊”就從集合中減去,每一次需要這樣操作的時候我們就稱之為“事件點”。
    每次遇到事件點的時候,我們就計算一次面積。就是與下個事件點的y的距離乘以這個區間集合的總長度就可以了。
    那么維護這個集合就可以用線段樹了。
    每次遇到新邊就cnt++,否則就cnt--。如果cnt不為0,說明這個節點有邊覆蓋...
    感覺還是樸素版更容易理解一些,寫起來很飄逸~
#include<iostream>
#include<cstdio>
#include<cassert>
#include<algorithm>
using namespace std;
const int V = 400;
int M,len;
struct segment_tree{
    int cnt; double sum;
} seg[V<<2];
struct segment{
    double l,r,y; int flag;
    segment(double x1=0,double x2=0,double y1=0,int p=0):l(x1),r(x2),y(y1),flag(p){}
} num[V];
bool operator < (segment a,segment b){
    return a.y< b.y;
}
double X[V],sum[V<<2];
inline void upt(int x){
    if(seg[x].cnt) seg[x].sum = sum[x];
    else if(x<M) seg[x].sum = seg[x<<1].sum+seg[x<<1|1].sum;
    else seg[x].sum=0;
}
double insert(int l,int r,int p){
//    cout<<l<<" "<<r<<" "<<p<<endl;
    for(l = l+M, r = r+M+2; l^r^1 ; l>>=1 , r>>=1){
        if(l&1^1){ seg[l^1].cnt += p; upt(l^1); }
        if(r&1){ seg[r^1].cnt += p; upt(r^1); }
        upt(l);upt(r);
    }
    upt(r);
    while(l){
        upt(l);    l >>=1;
    }
//    cout<<seg[1].sum<<endl;
    return seg[1].sum;
}
int search(double val){
    int l = 0, r = len;
    while(l<r){
        int mid = l+r >>1;
        if(X[mid]>= val) r = mid;
        else l = mid+1;
    }
    return r;
}
void build_tree(int n){
    for(int i=0;i<30;i++) if((1<<i) > n+1) {
            M = 1<<i; break;
    }
    for(int i=0;i<M*2;i++) sum[i] = seg[i].cnt = seg[i].sum = 0;
    for(int i=0;i<n-1;i++) sum[i+M+1] = X[i+1]-X[i];
    for(int i=M-1;i;i--) sum[i] = sum[i<<1]+sum[i<<1|1];
}
int main(){
    int n,__test=1;
    while(scanf("%d",&n)!=-1 && n){
        double x1,y1,x2,y2;
        int N = 0;
        for(int i =0 ;i<n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            X[N] = x1;
            num[N++] = segment(x1,x2,y1,1);
            X[N] = x2;
            num[N++] = segment(x1,x2,y2,-1);
        }
        sort(X,X+N);
        sort(num,num+N);
        len = 1;
        for(int i=1;i<N;i++){    
            if(X[i]!=X[i-1]) X[len++] = X[i];
        }
        build_tree(len);
        double ans = 0;
        for(int i=0;i<N-1;i++){
            int l = search(num[i].l);
            int r = search(num[i].r)-1;
            ans += insert(l,r,num[i].flag) * (num[i+1].y - num[i].y);
//            cout<<ans<<endl;
        }
//        cout<<ans<<endl;
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",__test++, ans);
    }
    return 0;
}
posted on 2012-05-08 16:49 西月弦 閱讀(778) 評論(0)  編輯 收藏 引用 所屬分類: 解題報告經典題目
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            午夜精品久久久久久99热软件| 欧美中在线观看| 99国产精品| 一区二区国产日产| 亚洲欧美日本伦理| 欧美中文在线视频| 久久免费国产| 亚洲人久久久| 99热这里只有精品8| 中文在线一区| 久久精品国产清高在天天线 | 亚洲国产精品成人| 亚洲日本视频| 亚洲欧美电影院| 久久精品一本| 欧美精品一区二区三区蜜桃| 国产精品久久久久99| 国产欧美69| 亚洲日本欧美日韩高观看| 在线中文字幕不卡| 久久精品一二三区| 亚洲精品激情| 欧美在线免费视屏| 欧美精品一区二区三区视频| 国产精品v亚洲精品v日韩精品 | 欧美激情一区二区三区蜜桃视频 | 亚洲视频高清| 欧美一区二区三区久久精品| 久久久不卡网国产精品一区| 媚黑女一区二区| 日韩一级黄色av| 久久综合99re88久久爱| 欧美丝袜一区二区三区| 在线观看亚洲视频| 午夜精品99久久免费| 亚洲成人中文| 欧美在线综合| 国产精品久久久久影院色老大| 精品成人一区二区| 亚洲一区日韩在线| 亚洲国产片色| 久久久久在线观看| 国产午夜精品全部视频播放| 99视频+国产日韩欧美| 乱人伦精品视频在线观看| 亚洲手机在线| 欧美视频在线观看免费| 亚洲国产婷婷| 欧美不卡视频一区| 欧美伊人影院| 国内精品99| 久久国产精品久久国产精品| 一区二区免费看| 欧美日韩国产在线播放| 亚洲狼人综合| 亚洲三级免费| 欧美精品在线观看91| 亚洲品质自拍| 91久久久久久| 国产精品海角社区在线观看| 一本色道久久综合亚洲精品按摩 | 激情亚洲一区二区三区四区| 久久精品成人一区二区三区| 亚洲资源在线观看| 国产欧美综合在线| 久久久久高清| 久久天堂成人| 亚洲区欧美区| 日韩一二三在线视频播| 欧美色网一区二区| 午夜精品久久久久久久久久久| 亚洲午夜精品久久| 国产免费成人av| 久久综合一区二区| 欧美r片在线| 亚洲无线视频| 亚洲一区精品在线| 国产日韩亚洲| 欧美激情一区二区三区不卡| 免费视频一区二区三区在线观看| 亚洲毛片在线看| 亚洲一区二区成人| 在线成人中文字幕| 亚洲精品一二三| 另类图片国产| 亚洲欧洲久久| 欧美色网一区二区| 久久国产精品久久w女人spa| 看欧美日韩国产| 亚洲男人av电影| 美国三级日本三级久久99| 亚洲视频在线视频| 欧美一级大片在线免费观看| 亚洲成人资源网| 中文在线一区| 亚洲精品社区| 欧美一区二区三区视频免费| 亚洲电影免费在线| 一区二区三区国产精华| 激情成人av在线| 一区二区激情小说| 亚洲国产精品成人精品| 国产精品99久久不卡二区| 亚洲大胆在线| 性做久久久久久免费观看欧美| 亚洲精品少妇30p| 久久婷婷亚洲| 香港久久久电影| 欧美日韩国产在线播放| 欧美成人精品福利| 国模精品一区二区三区色天香| 亚洲精品系列| 亚洲精品一级| 久久久久99| 久久精品观看| 国产欧美高清| 亚洲综合清纯丝袜自拍| 99国产精品久久久久老师 | 欧美一级免费视频| 亚洲视频一二| 欧美激情一区二区三区成人 | 校园春色国产精品| 亚洲视频在线二区| 欧美黑人国产人伦爽爽爽| 久久久亚洲高清| 国产精品日韩高清| 亚洲毛片av| 一区二区三区四区国产| 欧美大尺度在线观看| 两个人的视频www国产精品| 国产精品久在线观看| 99精品黄色片免费大全| 一本色道久久综合亚洲精品婷婷 | 亚洲国产日韩欧美一区二区三区| 国产一区观看| 久久精品国产精品亚洲| 久久夜色精品国产| 国产亚洲综合性久久久影院| 亚洲综合社区| 欧美一区二区三区日韩| 国产精品视频精品| 亚洲男人av电影| 亚洲女人天堂av| 欧美午夜久久| 午夜影视日本亚洲欧洲精品| 久久精品天堂| 久久不见久久见免费视频1| 欧美在线视频网站| 久久久不卡网国产精品一区| 激情成人亚洲| 欧美电影资源| 日韩午夜激情| 欧美一级欧美一级在线播放| 国产精品普通话对白| 欧美中文字幕精品| 欧美岛国激情| 亚洲一品av免费观看| 国产欧美日韩伦理| 久久乐国产精品| 亚洲精品一二| 久久精品九九| 日韩视频精品在线| 国产精品入口66mio| 久久精品女人天堂| 亚洲国产一区二区三区在线播| 99re热精品| 国产精品普通话对白| 久久精品成人欧美大片古装| 欧美 日韩 国产 一区| 亚洲电影免费| 欧美色另类天堂2015| 久久激情综合| 亚洲精品色婷婷福利天堂| 欧美专区在线| 亚洲精品日本| 国内精品久久久久久久影视蜜臀| 你懂的国产精品永久在线| 亚洲毛片在线看| 快播亚洲色图| 亚洲午夜女主播在线直播| 国产亚洲欧美日韩日本| 欧美巨乳在线观看| 欧美在线3区| 亚洲视频免费看| 欧美激情久久久久| 欧美在线看片| 亚洲视频每日更新| 亚洲国产成人久久综合一区| 国产精品手机在线| 欧美不卡视频| 久久久国产精彩视频美女艺术照福利| 99视频日韩| 亚洲第一中文字幕| 久久久久久久国产| 午夜精品婷婷| 亚洲色无码播放| 亚洲精品日韩综合观看成人91| 好看的日韩视频| 国产一区二区三区不卡在线观看| 国产精品v亚洲精品v日韩精品|