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

算法學社
記錄難忘的征途
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 西月弦 閱讀(772) 評論(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>
            蘑菇福利视频一区播放| 亚洲国产精品久久久久秋霞影院| 国产精品国产精品国产专区不蜜| 久久亚洲综合网| 午夜精品一区二区三区在线视 | 日韩视频第一页| 日韩亚洲欧美精品| 一本一本久久| 欧美中文字幕在线观看| 久久字幕精品一区| 久热综合在线亚洲精品| 欧美日韩另类国产亚洲欧美一级| 欧美日韩一区二区三区在线看 | 亚洲一区二区三区中文字幕| 亚洲视频在线观看| 欧美在线日韩| 亚洲美女黄色片| 亚洲桃色在线一区| 欧美综合国产| 免费成人av在线| 91久久中文| 亚洲欧美精品在线| 噜噜爱69成人精品| 国产精品高潮视频| 在线看视频不卡| 亚洲性人人天天夜夜摸| 久久久免费精品| 91久久极品少妇xxxxⅹ软件| 亚洲欧美日韩国产综合| 久久综合精品国产一区二区三区| 欧美日韩在线播放三区四区| 国内精品久久久久久久果冻传媒 | 香港成人在线视频| 亚洲国产高清在线| 欧美一区中文字幕| 欧美日韩三级视频| 亚洲国产日韩欧美综合久久| 性欧美长视频| 日韩一二三区视频| 美女国内精品自产拍在线播放| 欧美日韩中文字幕在线| 尤物yw午夜国产精品视频| 亚洲一级二级| 亚洲欧洲在线播放| 免费观看欧美在线视频的网站| 国产情人综合久久777777| 亚洲视频一二区| 亚洲欧洲精品天堂一级| 久久午夜精品一区二区| 国产一区三区三区| 欧美一区不卡| 亚洲午夜久久久久久久久电影网| 亚洲国产欧洲综合997久久| 性一交一乱一区二区洋洋av| 欧美视频一区在线| 一个色综合av| 亚洲黄色视屏| 欧美 日韩 国产一区二区在线视频 | 久久手机精品视频| 国产一区二区高清不卡| 亚洲欧美在线磁力| 亚洲一区久久| 国产久一道中文一区| 亚洲特黄一级片| 日韩一级在线观看| 欧美日韩精品欧美日韩精品一| 亚洲片在线资源| 亚洲国产精品成人一区二区| 欧美成年人网| 一区二区高清| 一区二区不卡在线视频 午夜欧美不卡在 | 亚洲国产欧美一区二区三区久久 | 国产欧美日韩一区| 欧美一级二级三级蜜桃| 亚洲午夜极品| 国产精品美女一区二区在线观看| 亚洲午夜久久久| 亚洲综合第一页| 国产午夜精品麻豆| 麻豆久久精品| 久久综合久久美利坚合众国| 精品电影一区| 在线亚洲一区二区| 一区二区三区**美女毛片| 国产精品国产自产拍高清av| 欧美伊人久久久久久久久影院 | 国产视频在线一区二区| 久久久欧美精品sm网站| 免费看黄裸体一级大秀欧美| 国产精品久久久久一区二区三区共| 亚洲欧美日韩在线不卡| 久久国产一区二区| 日韩视频在线你懂得| 亚洲制服av| 欧美黄色免费| 亚洲欧美中文字幕| 久久久欧美一区二区| 亚洲视频在线观看网站| 欧美一区二区日韩一区二区| 亚洲欧洲日本mm| 亚洲专区免费| 99国产精品一区| 欧美综合二区| 亚洲婷婷在线| 蘑菇福利视频一区播放| 亚洲天堂av高清| 美女图片一区二区| 欧美怡红院视频| 欧美精品色网| 老牛嫩草一区二区三区日本| 欧美日韩国产在线观看| 理论片一区二区在线| 欧美午夜一区二区福利视频| 美国三级日本三级久久99| 国产精品久久久一本精品| 久久免费精品视频| 国产精品久久| 亚洲人成在线播放网站岛国| 国产一区二区三区直播精品电影 | 亚洲黄色在线视频| 韩国免费一区| 亚洲免费在线观看视频| 日韩小视频在线观看| 久久久精品午夜少妇| 欧美一区二区视频在线| 欧美日韩精品高清| 亚洲高清色综合| 很黄很黄激情成人| 午夜伦欧美伦电影理论片| 亚洲一区二区三区在线| 欧美国产一区视频在线观看| 欧美一区二区日韩| 欧美四级在线观看| 亚洲精品中文在线| 亚洲精品少妇30p| 美女诱惑黄网站一区| 噜噜噜噜噜久久久久久91| 国产一区二区在线观看免费| 久久午夜精品一区二区| 国色天香一区二区| 欧美一区二区视频在线| 欧美在线播放视频| 国产亚洲一区二区三区在线观看| 亚洲午夜影视影院在线观看| 亚洲综合三区| 国产精品视频一区二区高潮| 亚洲午夜av在线| 欧美一区二区视频在线观看| 国产农村妇女毛片精品久久麻豆| 日韩视频永久免费观看| 亚洲五月六月| 国产精品一区视频| 欧美一区国产在线| 久久人人超碰| 亚洲国产精品一区制服丝袜 | 另类图片综合电影| 亚洲国产成人午夜在线一区 | 免费不卡在线视频| 亚洲欧洲精品一区二区精品久久久| 久久蜜桃av一区精品变态类天堂| 久久久久久电影| 亚洲国产精品尤物yw在线观看| 美女主播视频一区| 99国内精品| 久久精品国产亚洲a| 激情欧美亚洲| 欧美日韩国产成人在线观看| 中文在线资源观看网站视频免费不卡 | 亚洲免费久久| 久久国产婷婷国产香蕉| 亚洲第一二三四五区| 欧美日韩性视频在线| 欧美一区二区三区在线观看视频| 欧美在线免费视频| 亚洲国产视频直播| 国产精品r级在线| 久久综合五月天婷婷伊人| 夜夜嗨一区二区| 蜜桃久久av| 性色av一区二区三区在线观看 | 国产伦精品一区二区三区免费迷 | 亚洲电影免费观看高清完整版在线观看 | 日韩一级二级三级| 国产乱码精品一区二区三区五月婷 | 性高湖久久久久久久久| 亚洲国产mv| 欧美午夜久久| 久久露脸国产精品| 久久精品亚洲一区二区三区浴池| 日韩午夜激情av| 国产一区二区三区黄视频| 免费观看久久久4p| 久久久精彩视频| 亚洲美女诱惑| 六月天综合网| 亚洲区在线播放| 亚洲第一福利社区| 国产精品国产三级国产普通话三级| 久久er精品视频| 欧美一区二区免费|