Problem5887--三角形

5887: 三角形

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 12  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

给定 N 个三角形，和 M 条直线，直线要么平行于 x 轴，要么平行于 y 轴，问这 M 条直线分别穿过多少个三角形。

（一条直线穿过一个三角形，当且仅当这条直线可以将这个三角形分成两个面积均大于零的多边形）。


Input

输入的第一行包含一个正整数 N，表示三角形的个数。

接下来 N 行，每行三个坐标 (x1,y1)，(x2,y2)，(x3,y3) 表示三个点，且这三点不共线，描述一个三角形。所有坐标均为非负整数，三角形可以重叠。

接下来一行包含一个正整数 M，表示直线的条数。

接下来 M 行，每行一个字符串 `x = c` 或 `y = c`（注意等号两边的空格），描述一条直线。其中 `c` 为非负整数。

Output

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


Sample Input

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

Sample Output

0
1
1
2

HINT

### **【数据范围】**

对于 40% 的数据，M≤300；

另有 40% 的数据，所有三角形的坐标 <1000；

对于 100% 的数据，2≤N,M≤$10^5$，0≤x1,y1,x2,y2,x3,y3<$10^6$。



Source/Category

 

[Submit] [Status]