프로그램 명: coci_burek
제한시간: 1 초
N개의 삼각형이 있다. 이 삼각형들은 겹칠 수도 있다.
수평 방향 또는 수직 방향으로 이 삼각형들을 자를 때, 잘리는 삼각형의 개수를 구하는 프로그램을 작성하여라. 어떤 삼각형이 잘린다는 것은, 삼각형이 자르는 직선을 기준으로 두 영역으로 나뉜다는 것을 말한다.
입력 형식
-
첫 번째 줄에는 삼각형의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
-
두 번째 줄부터 N개의 줄에는 삼각형을 이루는 세 점의 좌표가 주어진다.
-
N+2번째 줄에는 자르려는 시도의 수 Q가 주어진다. (1 ≤ Q ≤ 100,000)
-
N+3번째 줄부터 Q개의 줄에는 자르는 직선의 방정식이 "x = c" 또는 "y = c" (공백 있음)꼴로 나타난다. c와 좌표의 값은 0 이상 1,000,000 이하이다.
출력 형식
각 시도에 대하여, 잘리는 삼각형의 수를 출력한다.
Baker Crumble has just baked N triangular burek2 pastries. Each pastry can be represented in the
Cartesian coordinate system as a triangle with vertices in integer coordinate points.
The baker's mischievous son Joey has just taken a large knife and started to cut the pastries. Each cut
that Joey makes corresponds to a horizontal (y = c) or vertical (x = c) line in the coordinate system.
Help the baker assess the damage caused by Joey's pastry cutting. Your task is to determine, for each
Joey's cut, how many pastries are affected (such that both the left and right parts of the cut pastry have
areas greater than zero).
입력
The first line of input contains the positive integer N (2 ≤ N ≤ 100 000), the number of burek pastries.
Each of the following N lines contains six nonnegative integers smaller than 106
. These numbers are, in order, the coordinates (x1 , y1), (x2 , y2), (x3 , y3) of the three pastry-triangle vertices. The three vertices will
not all be on the same line. The pastries can touch as well as overlap.
The following line contains the positive integer M (2 ≤ M ≤ 100 000), the number of cuts.
Each of the following M lines contains a single cut line equation: “x = c” or “y = c” (note the spaces
around the equals sign), where c is a nonnegative integer smaller than 106
.
출력
For each cut, output a line containing the required number of cut pastries.
입출력 예
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
output
0
1
1
2
input
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
output
3
2
3
2
출처:coci/2012-2013/contest6/4
번역:functionx
[질/답]
[제출 현황]
[푼 후(0)]