- 博客(0)
- 资源 (7)
空空如也
百度大楼竞价抢车位程序
一、竞价抢车位
题目描述
百度某分公司新建了一栋办公大楼,眼看就要落成了,同事们很快就可以入住新的大楼,但是随之而来也出现了一个新的问题:由于最近买车的同事数量激增,新落成的大楼的车位可能会十分的抢手;
为了有利于公平竞争,公司决定使用”竞价抢车位”方式决定那些车位的最后的使用权归属;
竞价抢车位的具体规则如下:
1,出价高的优先挑选车位
2,出价相同的按出价时间挑选车位,出价先者优先
3,知道所有车位被挑选完,活动结束
这可愁坏了A同学,新买的车当然需要一个车位,但是他又不想花太多的钱去竞拍,于是A同学通过各种渠道,打听来了一些有用的信息,以帮助自己分析如何去出价,才能确保自己以最低的价格获得一个车位,价格最小单位为元。公司规定,A至少要出1元才能参与竞价;
现在A手头已经得到了两张出价表格(不包括他自己),其中表格一已经汇总了各个价位出价的人数,比如:
100元 100人
200元 58 人
250元 90 人
…….
表格二则汇总了除了A以外尚没有投票的同事的目标价位
100元 98人
200元 30 人
250元 20 人
……
最后, A还去勘测了一下新的停车场的地形:
新的停车场是一个不规则的多边形(百度的建筑向来很有风格- -);
A依次测量了多边形的每个顶点,并且获得了坐标(均为整数),并且发现,只要是落在这个多边形内的整数坐标上的点,都被标记了出来(也就是说每个严格落在这个多边形内的整数点坐标上可以停一辆车)
如图所示 总共有16个点落在多边形内,我们可以认为共有16个车位
A需要你的帮助,马上计算出他至少要出什么样的价位,才能确保获得一个车位;
输入数据格式
首先有一行包含一个整数t,代表数据组数。接下来有t组数据。
每组数据首先有一行,包含三个整数n(1<=n<=10000),m(1<=m<=10000),k(1<=k<=1000)
接下来有n行 每行两个数 price_i count_i ,对应表格一
再接下来有m行 每行两个数 price_j count_j ,对应表格二(price_i之间互相不重复,price_j也是)
最后有k行 每行两个数 xi yi 表示停车场的形状(题目保证停车场是简单多边形。注意,既可能是顺时针,也可能是逆时针。)
注:所有price_i,count_i,price_j,count_j都在1到10000之间,所有xi,yi都在0到10000之间,而且是整数
输出数据格式
对每组数据,输出一行,代表一个价格;保证A只要出这个价格,就能得到一个车位。如果A无论出什么价格都无法得到车位,输出-1
样例
输入:
2
3 3 4
100 5
200 6
250 5
100 5
200 6
250 5
4 0
7 3
3 6
1 2
3 3 4
100 5
200 5
250 5
100 5
200 6
250 5
4 0
7 3
3 6
1 2
输出:
201
200
2011-06-01
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人