using System.Collections.Generic;
namespace CodeChef_200910_H2
{
///
/// split persons ; group by weight & strength
///
class PersonGroup : IComparable
{
public int weight;
public int strength;
public int person_num;
// when fill the min speed, some stength left.
public decimal left_strength;
public int CompareTo(PersonGroup other)
{
if (left_strength > other.left_strength) return 1;
if (left_strength < other.left_strength) return -1;
return 0;
}
}
class CaseItem
{
int caseIndex;
int person_number;
int total_weight = 0;
int total_strengh = 0;
decimal aver_speed = 0;
// for add person numbers quickly
PersonGroup[,] groupTable = new PersonGroup[51, 51];
// for sort by left_strength
List
private void buildIndex()
{
for (int weight = 0; weight <= 50; weight++)
{
for (int strength = 0; strength <= 50; strength++)
{
PersonGroup p = new PersonGroup();
groupTable[weight, strength] = p;
p.weight = weight + 60;
p.strength = strength + 50;
personList.Add(p);
}
}
}
public CaseItem(int index)
{
this.buildIndex();
caseIndex = index;
person_number = int.Parse(System.Console.ReadLine());
for (int i = 0; i < person_number; i++)
{
string s = Console.ReadLine();
string[] a = s.Split(' ');
int weight = int.Parse(a[0]) + 10;
int strength = int.Parse(a[1]);
groupTable[weight - 60, strength - 50].person_num++;
total_weight += weight;
total_strengh += strength;
}
aver_speed = decimal.Round((0.0M + total_strengh) / total_weight, 8);
}
private decimal test_min_speed(decimal v)
{
foreach (PersonGroup pg in personList)
{
pg.left_strength = pg.strength - v * pg.weight;
}
QuickSort
int start = 0;
int end = personList.Count - 1;
decimal min_v = int.MaxValue;
while (personList[start].person_num == 0) start++;
while (personList[end].person_num == 0) end--;
int min_start_index = start, min_end_index = end;
int start_left = personList[start].person_num;
int end_left = personList[end].person_num;
PersonGroup pstart = personList[start];
PersonGroup pend = personList[end];
while (start <= end)
{
if (pstart.left_strength + pend.left_strength < min_v)
{
min_v = pstart.left_strength + pend.left_strength;
min_start_index = start;
min_end_index = end;
}
if (start_left > end_left)
{
start_left -= end_left;
end--;
pend = personList[end];
end_left = pend.person_num;
}
else if (start_left == end_left)
{
start++;
end--;
pstart = personList[start];
pend = personList[end];
start_left = pstart.person_num;
end_left = pend.person_num;
}
else
{
end_left -= start_left;
start++;
pstart = personList[start];
start_left = pstart.person_num;
}
}
min_v = (0.0M + personList[min_start_index].strength + personList[min_end_index].strength) /
(personList[min_start_index].weight + personList[min_end_index].weight);
return decimal.Round(min_v, 8);
}
public void Execute()
{
decimal min_speed = aver_speed;
decimal test_speed;
do
{
test_speed = min_speed;
min_speed = test_min_speed(test_speed);
} while (min_speed != test_speed);
System.Console.WriteLine(decimal.Round(min_speed, 6).ToString());
}
public void QuickSort
where T : IComparable
{
if (high - low <= 0)
{
return;
}
else if (high - low == 1)
{
if (a[high].CompareTo(a[low]) < 0)
{
T t = a[high];
a[high] = a[low];
a[low] = t;
}
return;
}
int mid = (low + high) >> 1;
T pivot = a[mid];
T t2 = a[mid];
a[mid] = a[low];
a[low] = t2;
int up = low + 1;
int down = high;
do
{
while (up <= down && a[up].CompareTo(pivot) <= 0) up++;
while (up <= down && a[down].CompareTo(pivot) > 0) down--;
if (up < down)
{
T t = a[up];
a[up] = a[down];
a[down] = t;
}
} while (up < down);
a[low] = a[down];
a[down] = pivot;
if (low < down - 1)
{
QuickSort
}
if (down + 1 < high)
{
QuickSort
}
}
}
class Round
{
int case_num;
CaseItem[] items;
public Round()
{
case_num = 1;
items = new CaseItem[case_num];
for (int i = 0; i < case_num; i++)
{
items[i] = new CaseItem(i + 1);
}
}
public void Execute()
{
foreach (CaseItem item in items)
{
item.Execute();
}
}
}
class Program
{
static void Main(string[] args)
{
//BuildDebug();
(new Round()).Execute();
// Debug();
}
static void BuildDebug()
{
using (System.IO.StreamWriter writer = new System.IO.StreamWriter("a.in"))
{
int n = 100000;
Random r = new Random(1000000);
writer.WriteLine(n);
for (int i = 0; i < n; i++)
{
int w = r.Next(n) % 51 + 50;
int s = r.Next(n) % 51 + 50;
writer.WriteLine(w.ToString() + " " + s.ToString());
}
}
}
static void Debug()
{
System.IO.TextReader stdin = System.Console.In;
System.IO.TextWriter stdout = System.Console.Out;
try
{
using (System.IO.StreamReader reader = new System.IO.StreamReader("a.in"))
{
using (System.IO.StreamWriter writer = new System.IO.StreamWriter("out.txt"))
{
long datetime1 = DateTime.Now.Ticks;
System.Console.SetIn(reader);
System.Console.SetOut(writer);
(new Round()).Execute();
long datetime2 = DateTime.Now.Ticks;
DateTime datetime3 = DateTime.Now;
long seconds = (datetime2 - datetime1) / (datetime3.AddSeconds(1).Ticks - datetime3.Ticks);
System.Console.WriteLine(" second is : " + seconds.ToString());
System.Console.WriteLine(" ticks is : " + (datetime2 - datetime1).ToString());
System.Console.WriteLine(" ticks per seconds : " + (datetime3.AddSeconds(1).Ticks - datetime3.Ticks).ToString());
}
}
}
finally
{
System.Console.SetIn(stdin);
System.Console.SetOut(stdout);
}
}
}
}
Comments

