SP149 FSHEEP - Fencing in the Sheep
题目描述
有一位牧羊人赶他的羊到围栏里有些困难。经过几个小时徒劳的努力,他终于放弃了 ~~(牧羊犬呢)~~。这时,有些羊在围栏里,但有些还在外面闲逛。他筋疲力竭地走到围栏里的某个地方,从那里他可以看见整个围栏里的地方(没有任何栅栏挡道),并且开始数他的羊。请你协助他完成这个任务。
输入格式
第一行一个正整数 $t$,表示接下来有 $t$ 组数据。
接下来有 $t$ 组数据。对于每一组数据,第一行包含两个整数 $n$,$m$,表示多边形栅栏的顶点数以及羊的总数。保证 $3 \leq n \leq 100000$,$0 \leq m \leq 100000$。接下来 $n$ 行,第 $i$ 行有两个数 $x_{i}$,$y_{i}$,分别表示栅栏第 $i$ 个顶点的横坐标和纵坐标。按逆时针顺序给出。保证 $-32000 \leq x_{i},y_{i} \leq 32000$。接下来 $m$ 行,第 $j$ 行有两个数 $a_{j}$ 和 $b_{j}$,分别表示第 $j$ 只羊的横坐标和纵坐标。保证 $-32000 \leq a_{j},b_{j} \leq 32000$。牧羊人在 $(0,0)$ 点,保证在围栏内。 **坐在围栏上抽着香烟的羊(也就是恰好在围栏上的羊)也要计入总数。**
输出格式
共 $t$ 行,每行一个整数,表示在围栏里/围栏上的羊的数量。