A6246. 「POI2010」绵羊 Sheep
编程题
省选/NOI-
知识点
题目描述
**译自 POI 2010 Stage 2. Day 2「[Sheep](https://szkopul.edu.pl/problemset/problem/YjtAwdQrSiGcE_RLiEJpGiYE/site/?key=statement)」**
Byteasar 有一个凸多边形牧场，里面有一些羊。
现在 Byteasar 想要把这个凸多边形划分成若干三角形（划分线不能在牧场中相交，只能在顶点相交），使得每一个三角形里面的羊都有偶数只。
Byteasar 想知道有多少种方案，你只要输出方案数对 $m$ 取余后的结果即可。
Byteasar 有一个凸多边形牧场，里面有一些羊。
现在 Byteasar 想要把这个凸多边形划分成若干三角形（划分线不能在牧场中相交，只能在顶点相交），使得每一个三角形里面的羊都有偶数只。
Byteasar 想知道有多少种方案，你只要输出方案数对 $m$ 取余后的结果即可。
输入格式
第一行三个空格隔开的正整数 $n,k,m$ ，分别表示牧场的顶点数，羊的个数，以及模数。
接下来 $n$ 行，每行两个空格隔开的正整数 $x_i,y_i$ ，表示牧场的顶点坐标。
接下来 $k$ 行，每行两个空格隔开的正整数 $p_i,q_i$ ，表示羊的坐标。
接下来 $n$ 行，每行两个空格隔开的正整数 $x_i,y_i$ ，表示牧场的顶点坐标。
接下来 $k$ 行，每行两个空格隔开的正整数 $p_i,q_i$ ，表示羊的坐标。
输出格式
一行一个整数，表示方案数对 $m$ 取模的结果。
输入输出样例
输入 #1
5 4 10 5 5 3 0 -1 -1 -3 4 1 10 1 0 -1 0 1 6 -2 5
输出 #1
3
说明/提示
对于 $100\%$ 的数据， $4\le n\le 600,2\le k,m\le 20\ 000,2\mid k,-15\ 000\le x_i,y_i,p_i,q_i\le 15\ 000$ ，牧场的顶点坐标按顺时针顺序给出，保证羊严格在多边形内部。
Translated by vincent163
Translated by vincent163