![]() |
|
|
处在危险中的飞行员
|
||||
|
1941年二战期间,德国、意大利、匈牙利占领了南斯拉夫数月。在铁托的领导下,虽然面临法西斯的威胁,南斯拉夫仍然和敌人英勇斗争直到敌人逃跑,并付出了很大的生命代价。在东方,虽然德国和苏联于1939年8月23日签署了互不侵犯条约,但希特勒还是于1941年7月22日对苏联不宣而战。战争进入白热化阶段。10月2日,德国进攻莫斯科,妄图在10天内占领莫斯科。但是莫斯科坚持了整整两个月,牺牲了好几千人!在莫斯科保卫战和列宁格勒保卫战之后,苏联转入了战略反攻。 一天,一架苏联战机燃油耗尽,飞行员被迫跳伞。他很危险!但是他很快镇定下来,问题是他必须知道他是否在敌人的兵营之中,因为在兵营之外他没有什么可担心的。如果他没有那么走运,他必须取得在兵营内通行的密码。 兵营在一个水平面中,用栅栏包围。栅栏的投影是一个封闭多边形(不自交),其中n个顶点用迪卡尔坐标系的坐标表示。飞行员位于坐标(0,0)。飞行员可能在栅栏外或者栅栏内,但不会在栅栏上。并赢的密码是怎样的呢?给定两个素数p, q, p≠q,在兵营里很容易得到这两个数。这个密码表示,有多少个正整数不能表示为px+qy的形式(其中x, y≥0)。 例如给定p=3 ,q=5,有四个正整数不能表示为给定的形式,即1,2,4,7。所以密码是4。 输入 输入文件包含若干个测试点。对于每一个测试点,第一行包含一个整数n,满足3≤n≤16,且当n=0时表示输入结束。N表示多边形栅栏的顶点数。接下来的n行,每行包含两个实数xi and yi,用空格分开。接下一行是两个不同的素数p, q,2≤p, q≤1000,如上所述,可以由这两个素数得到密码。 坐标可能依顺时针或者逆时针给出。 输出 对于每个测试点,首先给出飞行员编号。下一行给出他是否处在危险之中(即他是否在兵营之内)。如果他在危险之中,在下一行中给出密码。 在每个测试点后输出一个空行。 Sample Output for Sample Input Pilot 2 |
||||
| 网站导航
| 关于曙光 | 联系我们
| 请提意见 Copyright © FuJian Sunshine Educational Info. Co.,Ltd. 福建曙光教育资讯有限公司 版权所有 |