• <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 閱讀(506) 評論(0)  編輯 收藏 引用 所屬分類: 數據結構
            热99RE久久精品这里都是精品免费 | 奇米综合四色77777久久| 国产精品99久久99久久久| 久久精品亚洲中文字幕无码麻豆| 国产福利电影一区二区三区久久老子无码午夜伦不| 久久亚洲AV成人无码| 久久影院综合精品| 色婷婷久久综合中文久久一本| 性高朝久久久久久久久久| 日产精品久久久一区二区| 青青草国产成人久久91网| 久久久久综合中文字幕| 18岁日韩内射颜射午夜久久成人| 色综合久久无码五十路人妻| 色综合久久夜色精品国产| av无码久久久久久不卡网站| 国产呻吟久久久久久久92| 国产亚洲综合久久系列| 久久天天躁狠狠躁夜夜2020一| 91精品国产综合久久香蕉| 精品久久久久久无码专区不卡| 亚洲精品久久久www| 欧美亚洲另类久久综合婷婷| 99久久精品国产毛片| 婷婷综合久久中文字幕| www.久久热.com| 久久国产精品一国产精品金尊| 欧美日韩久久中文字幕| 亚洲精品NV久久久久久久久久| 久久精品国产色蜜蜜麻豆| 久久久久久久久久免免费精品| 国产精品狼人久久久久影院| 久久久久国产一区二区三区| 久久久久亚洲av成人无码电影 | 国产成年无码久久久久毛片| 伊人久久精品无码av一区| 亚洲国产精品无码久久一线| 亚洲精品乱码久久久久久按摩| 69国产成人综合久久精品| 激情五月综合综合久久69| 久久AV高潮AV无码AV|