LYOJ 216 「雅礼集训 2017 Day10」拍苍蝇

## 题目描述
有一天，小A的母亲对他家里的卫生状况非常不满意，他的房间里有非常多的苍蝇。在母亲的威逼利诱下，小A拿起了苍蝇拍去消灭家里的苍蝇。然而，小A以前从来没有亲手消灭过任何一只苍蝇，以至于在他拿起苍蝇拍的那一刻，他对苍蝇起了怜悯之心——他不想伤害任何一只苍蝇。现在，小 A 面前的窗户上有$N$只苍蝇，他想知道有多少种方式可以在他拿起苍蝇拍拍窗户的时候，不伤害任何一只苍蝇。

窗户可以看作是一个左下角位于坐标系原点的矩形，苍蝇拍可以看作是一个多边形。在小 A 向窗户挥苍蝇拍时，对应多边形的顶点必须位于坐标系的整点上，并且苍蝇拍所在位置不能超过窗户所在范围。一只苍蝇会被伤害当且仅当小 A 用苍蝇拍拍向窗户时，苍蝇位于苍蝇拍内部、边上或顶点上。

## 输入格式
第一行三个正整数$X_p , Y_p$和$N$，分别表示窗户右上角的坐标和窗户上苍蝇的数量。
接下来 $N$行每行两个整数 $X、Y$，表示苍蝇在窗户上的位置。
接下来一行一个正整数 $K$，表示苍蝇拍的顶点数。
最后 K K 行每行两个正整数 $X_i,Y_i$，表示苍蝇拍上的第 $i$个顶点。按顶点给出的顺序，连接相邻的顶点（首尾相连），即为苍蝇拍外轮廓。
## 输出格式
输出仅一个正整数，表示苍蝇拍挥向窗户不伤害一只苍蝇的方案数。
## 样例
### 样例输入 1

4 5 2
1 3
3 4
4
0 0
2 0
2 2
0 2
### 样例输出 1

4
### 样例输入 2

5 5 3
1 4
1 3
2 2
3
4 7
6 3
7 6
### 样例输出 2

3
### 样例输入 3

6 7 2
2 5
4 5
8
1 4
3 3
3 1
5 3
7 4
5 5
4 7
3 5
### 样例输出 3
1
## 数据范围与提示
对于 $70\%$ 的数据， $1 \leq X_p, Y_p \leq 100$；
对于 $100\%$ 的数据， $1 \leq X_p, Y_p \leq 500, 0 \leq N \leq X_p \times Y_p, 3 \leq K \leq 100000, -10 ^ 9 \leq X_i, Y_i \leq 10 ^ 9$

## 题解

几何题总是说着容易，那就口头AC吧！

![233](http://on9i1rseh.bkt.clouddn.com/image/emoji/cantAC.jpg)

首先我们先那一个矩形框住多边形，然后以矩形左下角为参考点。现在我们算出$X_i * Y_i$的矩形中每个点作为参考点时会打死几只苍蝇。我们需要的只是预处理出一个$X_i * Y_i$的系数矩阵表示那些位置被多边形覆盖了（即为$1$），或者没有(即为$0$),那么把这个矩形和原苍蝇矩形卷积一下就可以了。
处理这个矩形我们使用扫描线即可。
复杂度$O((X_i * Y_i+K)*\log{X_i} + (X_i * Y_i)^2 *\log{(X_i*Y_i)} )$

wuvin

导航

最近发表

友情链接