• <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>
            #include? < iostream >
            #include?
            < algorithm >

            using ? namespace ?std;

            #define ?N?211

            struct ?Tree {
            ????
            double ?length;
            ????
            int ????cnt;
            ????Tree()
            {?length = ? 0 ;?cnt = ? 0 ;?}
            ????
            void ?init() {?length = ? 0 ;?cnt = ? 0 ;?}
            }
            tb[ 1610 ];

            double ?x1[N],?y1[N],?x2[N],?y2[N],?xx[N],?idx[N];
            int ?pos,?n;

            struct ?Line {
            ????
            double ?y,?x1,?x2;
            ????
            bool ?type;
            }
            line[N];

            bool ? operator < (?Line? const & ?a,?Line? const & ?b?) {
            ????
            return ?a.y < ?b.y;?}

            ????
            inline?
            int ?bsearch(? double ?value?) {
            ????
            int ?low = ? 1 ,?high = ?pos + ? 1 ,?mid;
            ????
            while (?low <= ?high?) {
            ????????mid
            = ?(low + ?high) >> ? 1 ;
            ????????
            if (?idx[mid] > ?value?)?high = ?mid - ? 1 ;
            ????????
            else ? if (?idx[mid] < ?value?)?low = ?mid + ? 1 ;
            ????????
            else ? return ?mid;
            ????}

            }


            void ?insert(? int ?rt,? int ?l,? int ?r,? int ?a,? int ?b?) {
            ????
            if (?l == ?a? && ?r == ?b?) {
            ????????tb[rt].length
            = ?idx[r] - ?idx[l];
            ????????tb[rt].cnt
            ++ ;? return ;?}

            ????
            ????
            if (?tb[rt].cnt != ? 0 ?) {
            ????????tb[rt
            << 1 ].cnt += ?tb[rt].cnt;?tb[(rt << 1 ) + 1 ].cnt += ?tb[rt].cnt;
            ????????tb[rt].cnt
            = ? 0 ;
            ????}

            ????
            ????
            int ?mid = ?(l + ?r) >> ? 1 ;
            ????
            if (?b <= ?mid?)?insert(?rt << ? 1 ,?l,?mid,?a,?b?);
            ????
            else ? if (?a >= ?mid?)?insert(?(rt << 1 ) + ? 1 ,?mid,?r,?a,?b?);
            ????
            else {
            ????????insert(?rt
            << ? 1 ,?l,?mid,?a,?mid?);
            ????????insert(?(rt
            << 1 ) + ? 1 ,?mid,?r,?mid,?b?);?}

            ????
            ????
            if (?tb[rt].cnt > ? 0 ?)?tb[rt].length = ?idx[r] - ?idx[l];
            ????
            else ?tb[rt].length = ?tb[rt << 1 ].length + ?tb[(rt << 1 ) + 1 ].length;
            }


            void ?del(? int ?rt,? int ?l,? int ?r,? int ?a,? int ?b?) {
            ????
            if (?l == ?a? && ?r == ?b?) {
            ????????tb[rt].cnt
            -- ;?? return ;
            ????}

            ????
            ????
            if (?tb[rt].cnt != ? 0 ?) {
            ????????tb[rt
            << 1 ].cnt += ?tb[rt].cnt;?tb[(rt << 1 ) + 1 ].cnt += ?tb[rt].cnt;
            ????????tb[rt].cnt
            = ? 0 ;
            ????}

            ????????
            ????
            int ?mid = ?(l + ?r) >> ? 1 ;
            ????
            if (?b <= ?mid?)?del(?rt << ? 1 ,?l,?mid,?a,?b?);
            ????
            else ? if (?a >= ?mid?)?del(?(rt << 1 ) + ? 1 ,?mid,?r,?a,?b?);
            ????
            else {
            ????????del(?rt
            << ? 1 ,?l,?mid,?a,?mid?);
            ????????del(?(rt
            << 1 ) + ? 1 ,?mid,?r,?mid,?b?);????
            ????}

            }


            void ?query(? int ?rt,? int ?l,? int ?r?) {
            ????
            if (?l + ? 1 == ?r?) {
            ????????
            if (?tb[rt].cnt > ? 0 ?)?tb[rt].length = ?idx[r] - ?idx[l];
            ????????
            else ?tb[rt].length = ? 0 ;
            ????????
            return ;?}

            ????
            ????
            if (?tb[rt].cnt != ? 0 ?) {
            ????????tb[rt
            << 1 ].cnt += ?tb[rt].cnt;?tb[(rt << 1 ) + 1 ].cnt += ?tb[rt].cnt;
            ????????tb[rt].cnt
            = ? 0 ;
            ????}

            ????
            ????
            int ?mid = ?(?l + ?r?) >> ? 1 ;
            ????query(?rt
            << 1 ,?l,?mid?);
            ????query(?(rt
            << 1 ) + ? 1 ,?mid,?r?);
            ????
            ????tb[rt].length
            = ?tb[rt << 1 ].length + ?tb[(rt << 1 ) + 1 ].length;
            }


            int ?main() {
            ????
            int ?test = ? 1 ;
            ????
            while (?scanf( " %d " , & n),?n != ? 0 ?) {
            ????????
            for (? int ?i = ? 0 ;?i <= ? 1600 ;? ++ i?)?tb[i].init();
            ????????
            ????????
            for (? int ?i = ? 0 ;?i < ?n;? ++ i?)? {
            ????????????scanf(
            " %lf%lf%lf%lf " ,?x1 + ?i,?y1 + ?i,?x2 + ?i,?y2 + ?i?);
            ????????????line[
            2 * i].y = ?y1[i];???line[ 2 * i].x1 = ?x1[i];?
            ????????????line[
            2 * i].x2 = ?x2[i];??line[ 2 * i].type = ? 0 ;
            ????????????
            ????????????xx[
            2 * i] = ?x1[i];?xx[ 2 * i + ? 1 ] = ?x2[i];
            ????????????line[
            2 * i + 1 ].y = ?y2[i];??line[ 2 * i + 1 ].x1 = ?x1[i];
            ????????????line[
            2 * i + 1 ].x2 = ?x2[i];?line[ 2 * i + 1 ].type = ? 1 ;
            ????????}

            ????????sort(?xx,?xx
            + ? 2 * ?n?);
            ????????sort(?line,?line
            + ? 2 * ?n?);
            ????????
            ????????pos
            = ? 1 ;?idx[ 1 ] = ?xx[ 0 ];
            ????????
            for (? int ?i = ? 1 ;?i < ? 2 * ?n;? ++ i?)
            ????????
            if (?xx[i] != ?xx[i - 1 ]?)?idx[ ++ pos] = ?xx[i];
            ????????
            ????????
            double ?ans = ? 0 ;
            ????????
            for (? int ?i = ? 0 ;?i < ? 2 * ?n - ? 1 ;? ++ i?) {
            ????????????
            int ?u = ?bsearch(?line[i].x1?),?v = ?bsearch(?line[i].x2?);
            ????????????
            ????????????
            if (?line[i].type == ? 0 ?)?insert(? 1 ,? 1 ,?pos,?u,?v?);
            ????????????
            else ?del(? 1 ,? 1 ,?pos,?u,?v?);
            ????????????
            ????????????query(?
            1 ,? 1 ,?pos?);
            ????????????ans
            += ?tb[ 1 ].length * ?(?line[i + 1 ].y - ?line[i].y?);
            ????????}

            ????????
            ????????printf(
            " Test?case?#%d\n " ,?test ++ ?);
            ????????printf(
            " Total?explored?area:?%.2lf\n\n " ,?ans?);
            ????}

            ????
            ????
            return ? 0 ;
            }






            #include? < iostream >
            #include?
            < algorithm >

            using ? namespace ?std;

            #define ?N?211

            struct ?Tree{
            ????
            double ?length;
            ????
            int ????cnt;
            ????Tree(){?length
            = ? 0 ;?cnt = ? 0 ;?}
            ????
            void ?init(){?length = ? 0 ;?cnt = ? 0 ;?}
            }tb[
            810 ];

            double ?x1[N],?y1[N],?x2[N],?y2[N],?xx[N],?idx[N];
            int ?pos,?n;

            struct ?Line{
            ????
            double ?y,?x1,?x2;
            ????
            bool ?type;
            }line[N];

            bool ? operator < (?Line? const & ?a,?Line? const & ?b?){
            ????
            return ?a.y < ?b.y;?}
            ????
            inline?
            int ?bsearch(? double ?value?){
            ????
            int ?low = ? 1 ,?high = ?pos + ? 1 ;
            ????
            while (?low <= ?high?){
            ????????
            int ?mid = ?(low + ?high) >> ? 1 ;
            ????????
            if (?idx[mid] > ?value?)?high = ?mid - ? 1 ;
            ????????
            else ? if (?idx[mid] < ?value?)?low = ?mid + ? 1 ;
            ????????
            else ? return ?mid;?}
            }

            inline?
            void ?update(? int ?rt,? int ?l,? int ?r?){
            ????
            if (?tb[rt].cnt > ? 0 ?)?tb[rt].length = ?idx[r] - ?idx[l];
            ????
            else ? if (?l + ? 1 == ?r?)?tb[rt].length = ? 0 ;
            ????
            else ?tb[rt].length = ?tb[rt << 1 ].length + ?tb[(rt << 1 ) + 1 ].length;
            }

            void ?deal(? int ?rt,? int ?l,? int ?r,? int ?a,? int ?b,? int ?t?){
            ????
            if (?a <= ?l? && ?b >= ?r?){
            ????????tb[rt].cnt
            += ?t;?update(?rt,?l,?r?);? return ;?}
            ????
            int ?mid = ?(l + ?r) >> ? 1 ;
            ????
            if (?a < ?mid?)?deal(?rt << ? 1 ,?l,?mid,?a,?b,?t?);
            ????
            if (?b > ?mid?)?deal(?(rt << 1 ) + ? 1 ,?mid,?r,?a,?b,?t?);
            ????update(?rt,?l,?r?);
            }

            int ?main(){
            ????
            int ?test = ? 1 ;
            ????
            while (?scanf( " %d " , & n),?n != ? 0 ?){
            ????????
            for (? int ?i = ? 0 ;?i <= ? 800 ;? ++ i?)?tb[i].init();
            ????????
            for (? int ?i = ? 0 ;?i < ?n;? ++ i?)?{
            ????????????scanf(
            " %lf%lf%lf%lf " ,?x1 + ?i,?y1 + ?i,?x2 + ?i,?y2 + ?i?);
            ????????????line[
            2 * i].y = ?y1[i];???line[ 2 * i].x1 = ?x1[i];?
            ????????????line[
            2 * i].x2 = ?x2[i];??line[ 2 * i].type = ? 0 ;
            ????????????
            ????????????xx[
            2 * i] = ?x1[i];?xx[ 2 * i + ? 1 ] = ?x2[i];
            ????????????line[
            2 * i + 1 ].y = ?y2[i];??line[ 2 * i + 1 ].x1 = ?x1[i];
            ????????????line[
            2 * i + 1 ].x2 = ?x2[i];?line[ 2 * i + 1 ].type = ? 1 ;
            ????????}
            ????????sort(?xx,?xx
            + ? 2 * ?n?);????sort(?line,?line + ? 2 * ?n?);
            ????????pos
            = ? 1 ;?idx[ 1 ] = ?xx[ 0 ];
            ????????
            for (? int ?i = ? 1 ;?i < ? 2 * ?n;? ++ i?)
            ????????
            if (?xx[i] != ?xx[i - 1 ]?)?idx[ ++ pos] = ?xx[i];
            ????????
            ????????
            double ?ans = ? 0 ;
            ????????
            for (? int ?i = ? 0 ;?i < ? 2 * ?n - ? 1 ;? ++ i?){
            ????????????
            int ?u = ?bsearch(?line[i].x1?),?v = ?bsearch(?line[i].x2?);
            ????????????
            if (?line[i].type == ? 0 ?)?deal(? 1 ,? 1 ,?pos,?u,?v,? 1 ?);
            ????????????
            else ?deal(? 1 ,? 1 ,?pos,?u,?v,? - 1 ?);
            ????????????
            ????????????ans
            += ?tb[ 1 ].length * ?(?line[i + 1 ].y - ?line[i].y?);
            ????????}
            ????????printf(
            " Test?case?#%d\n " ,?test ++ ?);
            ????????printf(
            " Total?explored?area:?%.2lf\n\n " ,?ans?);
            ????}
            ????
            ????
            return ? 0 ;
            }
            posted on 2009-08-06 00:49 Darren 閱讀(511) 評論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)
            欧美精品久久久久久久自慰| 久久综合久久自在自线精品自| 亚洲一区精品伊人久久伊人| 综合久久给合久久狠狠狠97色| 欧美综合天天夜夜久久| 久久毛片一区二区| 亚洲欧美国产精品专区久久| 久久夜色精品国产欧美乱| 色狠狠久久AV五月综合| 91精品婷婷国产综合久久| 久久精品国产亚洲一区二区| 久久人人爽人人爽人人爽| 国产精品成人久久久| 国产精品一区二区久久精品无码 | 久久天天躁狠狠躁夜夜96流白浆| 久久精品国产福利国产秒| 中文字幕无码久久精品青草| 精品国产乱码久久久久软件| 99久久国产综合精品五月天喷水 | 伊人热热久久原色播放www| 99精品国产在热久久 | 欧美成人免费观看久久| 日本精品久久久中文字幕| 欧美精品一本久久男人的天堂| 久久午夜羞羞影院免费观看| 国产成人精品久久免费动漫 | 久久ZYZ资源站无码中文动漫| yy6080久久| 九九精品99久久久香蕉| 久久久久久午夜成人影院| 免费观看成人久久网免费观看| av无码久久久久久不卡网站 | Xx性欧美肥妇精品久久久久久| 99久久国产精品免费一区二区| 国产精品亚洲综合久久 | 99久久婷婷国产综合精品草原 | 国产精品成人久久久久三级午夜电影| 久久成人国产精品| 久久这里只精品国产99热| 97精品伊人久久大香线蕉| 亚洲中文久久精品无码ww16|