logo AlgoBeat OnlineJudge
登录 注册

#102881. [BZOJ 2881] [Ceoi2000] LandsScape

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一座由 个转折点 顺次连接 而成的山峰以及 颗在同一水平高度 的星星。

一颗星星 能照亮一个点 ,当且仅当 被点亮并且 的连线 不穿过 山峰,但和山峰的某条边重合是被允许的。

现在需要求出最少点亮多少颗星星可以照亮山峰上的每一个点,或者报告无解。

输入格式

第一行一个整数

第二行一个整数

接下来一行 个整数,第 个整数 表示第 颗星星位于

接下来一行一个整数

接下来 ​ 行每行两个数 ​ 表示一个转折点的坐标。

输出格式

如果可以通过点亮某些星星使得山峰上每一个点都被照亮,则输出最少需要点亮星星的数目,否则输出一行 Shit..I can't see rins... 表示无解。

样例

样例输入 #1

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

样例输出 #1

3

样例解释

下图即为样例 #1 的情况。

数据范围与提示

对于 ​ 的数据,无解;

对于 的数据,

对于另外 的数据,

对于 ​ 的数据,