有一座由 个转折点 顺次连接 而成的山峰以及 颗在同一水平高度 的星星。
一颗星星 能照亮一个点 ,当且仅当 被点亮并且 与 的连线 不穿过 山峰,但和山峰的某条边重合是被允许的。
现在需要求出最少点亮多少颗星星可以照亮山峰上的每一个点,或者报告无解。
第一行一个整数 。
第二行一个整数 。
接下来一行 个整数,第 个整数 表示第 颗星星位于 。
接下来一行一个整数 。
接下来 行每行两个数 表示一个转折点的坐标。
如果可以通过点亮某些星星使得山峰上每一个点都被照亮,则输出最少需要点亮星星的数目,否则输出一行 Shit..I can't see rins... 表示无解。
Shit..I can't see rins...
3 2 7 14 9 10 0 80 3 10 5 70 8 50 10 40 12 20 13 90 14 40 17
3
下图即为样例 #1 的情况。
对于 的数据,无解;
对于 的数据,;
对于另外 的数据,;
对于 的数据,,,,。