#P2464. Brownie Points II

Brownie Points II

本题没有可用的提交语言。

题目描述

斯坦和奥利玩OddBrowniePointsOdd Brownie Points游戏。一些布朗尼点位于平面上,在整数坐标。斯坦先打,在飞机上放一条垂直线。这条线必须穿过一个布朗尼点,并且可能跨越许多(使用相同的x坐标)。然后奥利放置一条水平线,必须穿过垂直线已经穿过的布朗尼点。

这些线将飞机分成四个象限。包含任意大正坐标的点的象限是右上角象限。

球员根据象限中的布朗尼点数得分。如果一个布朗尼点被一条线穿过,它不算数。斯坦在右上角和左下角的每个(未交叉的)布朗尼点获得一个点。奥利在左上角和右下角的每个(未交叉的)布朗尼点获得一个点。

斯坦和奥利都试图最大化自己的分数。当斯坦上场时,他会考虑答案,并选择一条最大化他最小可能得分的线。

输入

输入包含多个测试用例。每个测试用例的数据都出现在输入线的序列上。每个测试用例的第一行包含一个正奇数整数1<n<20000001 < n < 2000000,即布朗尼点数。以下 nn 行中的每一条都包含两个整数,即布朗尼点的水平(x)(x) 和垂直(y)(y)坐标。没有两个布朗尼点占据同一个地方。输入以包含 0 的行结尾(而不是 test 的 n ) 。

输出

对于每个输入测试,请以以下格式打印一行输出。第一个数字是斯坦可以为自己保证的最大分数。剩下的数字是奥利的可能(高)分数,顺序越来越高。 输入数 1

11
3 2
3 3
3 4
3 6
2 -2
1 -3
0 0
-3 -3
-3 -2
-3 -4
3 -7
0

输出数位 1

Stan: 7; Ollie: 2 3;

来源

滑铁卢当地2005.06.11