#P2881. [Ceoi2000] LandsScape

[Ceoi2000] LandsScape

题目描述

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

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

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

输入格式

第一行一个整数 hh。

第二行一个整数 tt。

接下来一行 tt 个整数,第 ii 个整数 aia_i 表示第 ii 颗星星位于 (ai,h)(a_i,h)。

接下来一行一个整数 nn。

接下来 nn​ 行每行两个数 x,yx,y​ 表示一个转折点的坐标。

输出格式

如果可以通过点亮某些星星使得山峰上每一个点都被照亮,则输出最少需要点亮星星的数目,否则输出一行 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

样例解释

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

数据规模与约定

对于 10%10\%​ 的数据,无解;

对于 20%20\% 的数据,t=1t=1;

对于另外 30%30\% 的数据,2≤n≤32\leq n\leq 3;

对于 100%100\%​ 的数据,1≤t≤1001\leq t\leq 100,2≤n≤1002\leq n\leq 100,0≤y<h≤1040\leq y< h\leq 10^4,0≤x≤1030\leq x\leq 10^3。