#include
<
iostream
>
#include
<
algorithm
>
using
namespace
std;
#define
N 2110
struct
Tree
{
double
length, len;
int
cnt;
Tree()
{ length
=
0
; cnt
=
0
; }
void
init()
{ length
=
0
; cnt
=
0
; len
=
0
; }
}
tb[
10100
];
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 ) 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;
}
inline
void
update2(
int
rt,
int
l,
int
r )
{
if
( tb[rt].cnt
>
1
) tb[rt].len
=
idx[r]
-
idx[l];
else
if
( tb[rt].cnt
==
1
) tb[rt].len
=
tb[rt
<<
1
].length
+
tb[(rt
<<
1
)
+
1
].length;
else
tb[rt].len
=
tb[rt
<<
1
].len
+
tb[(rt
<<
1
)
+
1
].len; }
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 ); update2( 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 ); update2( rt, l, r );
}
int
main()
{
int
test
=
1
;
scanf(
"
%d
"
,
&
test );
while
( test
--
)
{
scanf(
"
%d
"
,
&
n);
for
(
int
i
=
0
; i
<=
10000
;
++
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
].len
*
( line[i
+
1
].y
-
line[i].y );
}
printf(
"
%.2lf\n
"
, ans );
}
return
0
;
}
posted on 2009-08-06 09:59
Darren 阅读(587)
评论(0) 编辑 收藏 引用 所属分类:
数据结构