[Ceoi2000] LandsScape

时间限制:10s      空间限制:128MB

题目描述

 话说rins操作技术太无下限了,出门装手一抽就买了2个鞋子,结果没钱了于是rins一路被压榨,走上上爆塔,走下下路崩,无奈之下他硬着头皮来到了中路,然后就被pcx虐残了..rins发现自己只有-1滴血,万幸自己无下限..于是掉头就跑,奔到了野区的山岭上,xx紧随其后,带着1000米高精准爆菊神器准备收了这FB。不过此时天色已晚,pcx视力不太好,只有有光的地方才能被他打到,已知天空高度为sky,有t个一闪一闪的小星星位于不同位置,如果山上某一点与星星i的连线不穿过山上其他点刚好与山整条线重合,则称星星i可以照亮该点,rins开了疾风步,可以躲在任意一点,那么pcx是否能爆了rins,得到fb呢?如果能,则至少要利用几个星星呢?


输入格式

 第一行 sky
第二行 t
33+t-1每行一个数,第i个星星的横坐标,保证星星横坐标已从小到大排好
3+t n
接下来n每行两个数,表示山的转折点的纵坐标和横坐标,保证横坐标已从小到大排好


输出格式

 如果可以虐死rins,则输出最少利用的星星个数;
   否则输出“Shit..I can't see rins...”不包括引号。


样例输入

  100
3
2 7 14
9
10 0
80 3
10 5
70 8
50 10
40 12
20 13
90 14
40 17

样例输出

 3

提示

数据范围与约定
  对于10%数据 rins RP比较好
对于20%的数据:t=1
 对于另外30%的数据:2<=n<=3
对于100%的数据:sky<=10000
t<=100
2<=n<=100
0<=所有山的纵坐标<sky
0<=所有横坐标<=1000


题目来源

没有写明来源

Menuappsclose