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

#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 閱讀(520) 評論(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>
            久久国产精品久久久| 在线国产精品播放| 欧美日本亚洲| 亚洲成人直播| 久久久国产午夜精品| 一本色道久久综合亚洲91| 羞羞漫画18久久大片| 日韩天堂在线观看| 久久精品欧美| 91久久精品网| 夜夜精品视频| 欧美系列精品| 久久久久久久久伊人| 久久精品成人一区二区三区蜜臀| 亚洲欧美日本伦理| 亚洲欧美日韩在线一区| 日韩亚洲欧美一区| 国产精品一区视频网站| 免费成人性网站| 免费欧美电影| 免费av成人在线| 亚洲综合色激情五月| 亚洲在线中文字幕| 亚洲一区二区在| 一本色道久久综合一区| 亚洲人成绝费网站色www| 亚洲激情第一区| 国产自产v一区二区三区c| 一区二区免费看| 99在线热播精品免费| 国产精品九九久久久久久久| 亚洲国产精品成人综合色在线婷婷 | 亚洲男女毛片无遮挡| 99国产精品99久久久久久| 日韩一区二区精品| 欧美成人亚洲| 亚洲国产91精品在线观看| 欧美福利视频在线观看| 激情亚洲网站| 欧美日韩伦理在线免费| 午夜精品在线视频| 国内精品久久久| 亚洲黄色免费网站| 久久精品国产99国产精品澳门| 亚洲国产精品一区二区第一页 | 欧美成人午夜剧场免费观看| 国产欧美日韩高清| 亚洲在线免费视频| 亚洲黑丝在线| 欧美成人日本| 亚洲欧洲一级| 欧美激情精品| 免费中文日韩| 亚洲国产导航| 亚洲国产导航| 欧美91精品| 亚洲人体影院| 亚洲国产日韩一级| 欧美激情综合色综合啪啪| 最新日韩欧美| 91久久久亚洲精品| 欧美日韩黄视频| 夜夜嗨av一区二区三区免费区| 欧美激情第8页| 欧美顶级少妇做爰| 99精品免费视频| 99国内精品| 国产精品一区二区三区成人| 午夜精品久久久久久久| 亚洲欧美日韩国产成人| 国产一区二区成人| 欧美freesex交免费视频| 久热re这里精品视频在线6| 亚洲高清资源| 亚洲欧洲在线一区| 欧美三级电影大全| 久久精品国产精品| 久久亚洲私人国产精品va媚药| 亚洲福利视频网站| 亚洲人成在线影院| 国产精品高潮呻吟久久av无限| 亚洲综合视频网| 久久激五月天综合精品| 91久久久亚洲精品| 一区二区三区久久| 国产一区二区三区高清播放| 毛片一区二区三区| 欧美人与性动交α欧美精品济南到 | 久久久久88色偷偷免费| 久久精品二区亚洲w码| 在线观看久久av| 日韩网站在线观看| 国产自产在线视频一区| 亚洲黄色高清| 欧美一区激情| 久久久久国产精品一区| 亚洲日本va午夜在线影院| 宅男精品导航| 亚洲国产精品成人精品| 亚洲午夜小视频| 亚洲激情二区| 午夜亚洲视频| 一区二区日韩伦理片| 欧美专区亚洲专区| 亚洲手机在线| 免费亚洲一区二区| 久久精品国产精品亚洲精品| 欧美成人免费网站| 久久久一区二区| 欧美性jizz18性欧美| 美女精品国产| 国产日韩一级二级三级| 亚洲精品中文字幕女同| 国模大胆一区二区三区| 亚洲图片欧美午夜| 99在线|亚洲一区二区| 欧美在线一区二区三区| 亚洲综合欧美| 欧美精品亚洲精品| 欧美国产精品人人做人人爱| 国产情人节一区| 亚洲性夜色噜噜噜7777| 国产精品99久久99久久久二8 | 欧美福利影院| 国产一区二区高清不卡| 一区二区欧美亚洲| 在线综合亚洲欧美在线视频| 免费成人高清在线视频| 美女久久网站| 在线成人激情视频| 久久狠狠久久综合桃花| 久久精品国产精品亚洲精品| 国产视频综合在线| 欧美一区二区三区的| 性欧美大战久久久久久久免费观看| 欧美日韩综合久久| 亚洲色图制服丝袜| 亚洲自拍偷拍麻豆| 国产精品久久久免费| 在线综合亚洲| 久久国产直播| 一区二区在线观看av| 久久久久久夜精品精品免费| 麻豆精品国产91久久久久久| 激情欧美丁香| 免费在线播放第一区高清av| 欧美激情第10页| 在线亚洲免费| 国产精品网站在线| 久久成人免费视频| 欧美aa在线视频| 中日韩高清电影网| 国产精品大全| 久久精品亚洲一区二区| 亚洲大片av| 中国成人黄色视屏| 国产日韩欧美综合| 榴莲视频成人在线观看| 亚洲人午夜精品| 性色av一区二区三区| 精品不卡一区| 久久国内精品自在自线400部| 国内自拍一区| 麻豆av一区二区三区久久| 亚洲国产精品成人| 亚洲欧美日本国产有色| 国产亚洲福利社区一区| 久久综合狠狠综合久久综青草 | 久久精品国产久精国产爱| 美女在线一区二区| 一区二区三区偷拍| 国产一区在线看| 欧美日韩大陆在线| 久久成人久久爱| 亚洲国产黄色| 久久精品91久久香蕉加勒比 | 欧美特黄一级| 久久久久久久久蜜桃| 亚洲美女色禁图| 久久综合九色欧美综合狠狠| 最新日韩中文字幕| 国产一区自拍视频| 国产精品www994| 欧美成人免费va影院高清| 香蕉国产精品偷在线观看不卡| 欧美成人精品在线观看| 亚洲伊人网站| 日韩午夜剧场| 狠狠色综合网站久久久久久久| 欧美日韩视频在线一区二区 | 一区二区三欧美| 亚洲第一在线综合在线| 久久精品亚洲国产奇米99| 女人色偷偷aa久久天堂| 亚洲一区免费视频| 亚洲免费成人| 亚洲日本欧美| 美女视频黄a大片欧美| 欧美一区91| 亚洲一区区二区|