#include<stdio.h>
#include <stdlib.h>
typedef struct SNode
{
short int v;
short int p;
}SNode;
typedef struct SLine
{
short int len;
SNode nodes[400];
}SLine;
SLine line;
SLine tmp[2];
int cb_fCampNode(const void* p_a,const void* p_b)
{
return ((const SNode*)p_a)->v == ((const SNode*)p_b)->v?
(((const SNode*)p_a)->p - ((const SNode*)p_b)->p )
:(((const SNode*)p_a)->v - ((const SNode*)p_b)->v);
}
void fInitCheck(SLine& line)
{
short int len = line.len;
short int min = -1;
for (int j = len -1;j>=0;--j)
{
if(line.nodes[j].p == -1)
{
continue;
}
if(min == -1)
{
min = line.nodes[j].p;
}else
{
if(min <= line.nodes[j].p)
{
line.nodes[j].p = -1;
}else
{
min = line.nodes[j].p;
}
}
}
int n =0;
for(int j = 0 ; j< len;++j)
{
if (line.nodes[j].p != -1 )
{
if(n!=j)
{
line.nodes[n++] = line.nodes[j];
}else
{
++n;
}
}
}
line.len = n;
}
void fInit(SLine& line)
{
qsort(line.nodes,line.len,sizeof(SNode),cb_fCampNode);
int len = line.len;
for (int j = 0; j < len-1;++j)
{
if(line.nodes[j].v == line.nodes[j+1].v)
{
line.nodes[j+1].p = -1;
}
}
fInitCheck(line);
}
inline void fLineAddNode(SLine& line,int v,int p)
{
line.nodes[line.len].v = v;
line.nodes[line.len++].p = p;
}
int main()
{
int n;
int number;
scanf("%d",&n);
while(n-- > 0)
{
tmp[1].len = 0;
tmp[0].len = 0;
scanf("%d",&number);
for (int i = 0;i<number;++i)
{
tmp[i&0x1].len = 0;
scanf("%d",&line.len);
for (int j = 0; j < line.len;++j)
{
scanf("%d %d",&(line.nodes[j].v),&(line.nodes[j].p));
}
fInit(line);
if(tmp[1 - i&0x1].len == 0)
{
for (int j =0;j<line.len;++j)
{
fLineAddNode(tmp[i&0x1],line.nodes[j].v,line.nodes[j].p);
}
}else
{
for(int m = 0,n=0;m < tmp[1-i&0x1].len&&n<line.len;)
{
if(line.nodes[n].v == tmp[1-i&0x1].nodes[m].v)
{
fLineAddNode(tmp[i&0x1],line.nodes[n].v,line.nodes[n++].p + tmp[1-i&0x1].nodes[m++].p);
}else if(line.nodes[n].v < tmp[1-i&0x1].nodes[m].v)
{
fLineAddNode(tmp[i&0x1],line.nodes[n].v,line.nodes[n++].p + tmp[1-i&0x1].nodes[m].p);
}else if(line.nodes[n].v > tmp[1-i&0x1].nodes[m].v)
{
fLineAddNode(tmp[i&0x1],tmp[1-i&0x1].nodes[m].v,line.nodes[n].p + tmp[1-i&0x1].nodes[m++].p);
}
}
fInitCheck(tmp[i&0x1]);
}
}
double d_out = 0;
for (int i =0;i<tmp[(number-1)%2].len;++i)
{
double tmp_d = ((double)tmp[(number-1)%2].nodes[i].v)/tmp[(number-1)%2].nodes[i].p;
if(tmp_d > d_out)
{
d_out = tmp_d;
}
}
printf("%0.3f\n",d_out);
}
}
转载请注明原文地址: https://ju.6miu.com/read-679723.html
