• <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) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)
            久久免费小视频| 久久九九久精品国产| 久久国产精品77777| 久久精品一区二区三区不卡| 国产精品伦理久久久久久| 国产精品久久久香蕉| 久久国产精品一国产精品金尊 | 97久久婷婷五月综合色d啪蜜芽 | 久久久精品国产sm调教网站| 97久久综合精品久久久综合| 久久久久18| 99久久精品毛片免费播放| 久久精品国产一区二区| 欧美大香线蕉线伊人久久| 久久91精品综合国产首页| 久久精品a亚洲国产v高清不卡| 久久性精品| 国产精品久久精品| 伊人久久综合无码成人网| 久久精品国产影库免费看| 亚洲精品美女久久777777| 国产精品欧美久久久久天天影视| 久久婷婷激情综合色综合俺也去| 大蕉久久伊人中文字幕| 久久久久无码精品国产| 日韩人妻无码精品久久久不卡| 中文成人无码精品久久久不卡| 一本大道加勒比久久综合| 中文无码久久精品| 亚洲国产精品狼友中文久久久 | 亚洲精品高清一二区久久| 国产成人久久精品激情 | 四虎亚洲国产成人久久精品| 精品久久久久久| 国产成人久久激情91| 久久久久亚洲AV无码观看 | 久久人妻AV中文字幕| 亚洲国产一成久久精品国产成人综合| 国产午夜精品理论片久久| 97久久超碰成人精品网站| 国产91色综合久久免费分享|