[COCI2012-2013#6] BUREK

题目背景

COCI

题目描述

给定 $N$ 个三角形，和 $M$ 条直线，直线要么平行于 $x$ 轴，要么平行于 $y$ 轴，问这 $M$ 条直线分别穿过多少个三角形。 **（一条直线穿过一个三角形，当且仅当这条直线可以将这个三角形分成两个面积均大于零的多边形）。**

输入输出格式

输入格式

输入的第一行包含一个正整数 $N$，表示三角形的个数。接下来 $N$ 行，每行三个坐标 $(x_1,y_1)$，$(x_2,y_2)$，$(x_3,y_3)$ 表示三个点，且这三点不共线，描述一个三角形。所有坐标均为非负整数，三角形可以重叠。接下来一行包含一个正整数 $M$，表示直线的条数。接下来 $M$ 行，每行一个字符串 `x = c` 或 `y = c`（注意等号两边的空格），描述一条直线。其中 `c` 为非负整数。

输出格式

对于每一条直线输出一个整数，表示它穿过的三角形的个数。

输入输出样例

输入样例 #1

3
1 0 0 2 2 2
1 3 3 5 4 0
5 4 4 5 4 4
4
x = 4
x = 1
y = 3
y = 1

输出样例 #1

输入样例 #2

4
2 7 6 0 0 5
7 1 7 10 11 11
5 10 2 9 6 8
1 9 10 10 4 1
4
y = 6
x = 2
x = 4
x = 9

输出样例 #2

说明

**【数据范围】** 对于 $40 \%$ 的数据，$M \le 300$；另有 $40 \%$ 的数据，所有三角形的坐标 $< 1000$；对于 $100 \%$ 的数据，$2 \le N,M \le 10^5$，$0 \le x_1,y_1,x_2,y_2,x_3,y_3 < 10^6$。