#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 阅读(519)
评论(2) 编辑 收藏 引用 所属分类:
图论 、
搜索