开发工具:
文件大小: 2kb
下载次数: 0
上传时间: 2011-06-01
详细说明： 一、竞价抢车位 题目描述 百度某分公司新建了一栋办公大楼，眼看就要落成了,同事们很快就可以入住新的大楼,但是随之而来也出现了一个新的问题:由于最近买车的同事数量激增,新落成的大楼的车位可能会十分的抢手; 为了有利于公平竞争,公司决定使用”竞价抢车位”方式决定那些车位的最后的使用权归属; 竞价抢车位的具体规则如下: 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 ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
