#include
<
iostream
>
#include
<
set
>
#include
<
limits
>
using
namespace
std;

struct
Node

{
int
broad, price;

Node()
{}
Node(
int
&
a,
int
&
b)
:broad(a),price(b)

{}
}
;

Node data[
100
][
100
];
int
length[
100
];


int
main()

{
int
test;
scanf(
"
%d
"
,
&
test);

while
( test
--
)

{
int
n;
set
<
int
>
br;

scanf(
"
%d
"
,
&
n);

for
(
int
i
=
0
; i
<
n;
++
i )

{
int
d,x,y;
scanf(
"
%d
"
,
&
d);

length[i]
=
d;
for
(
int
j
=
0
; j
<
d;
++
j )

{
scanf(
"
%d%d
"
,
&
x,
&
y);
data[i][j]
=
Node(x,y);

br.insert(x);
//
Save all broad , use set to avoid repeating
}
}
set
<
int
>
::iterator pos;
double
max
=
numeric_limits
<
double
>
::min();
for
( pos
=
br.begin (); pos
!=
br.end ();
++
pos )
//
for every broad
{
int
t
=
*
pos;
int
total
=
0
;
bool
isok
=
false
;

for
(
int
i
=
0
; i
<
n;
++
i )
//
n devices
{
int
M
=
INT_MAX;

for
(
int
j
=
0
; j
<
length[i];
++
j )
if
( data[i][j].broad
>=
t
&&
data[i][j].price
<
M )
M
=
data[i][j].price;
//
find the min price
if
( M
==
INT_MAX )

{
isok
=
true
;
break
;
}
total
+=
M;
}
if
( isok )
continue
;

if
( (
double
)t
/
(
double
)total
>
max ) max
=
(
double
)t
/
(
double
)total;
//
update
}
printf(
"
%.3lf\n
"
, max );
}
return
0
;
}
posted on 2008-10-01 22:06
Darren 阅读(524)
评论(2) 编辑 收藏 引用 所属分类:
图论 、
搜索