#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 阅读(493)
评论(0) 编辑 收藏 引用 所属分类:
数据结构