#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)