페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1688

삼각형 자르기 (BUREK) 1초 32MB

문제

N개의 삼각형이 있다. 이 삼각형들은 겹칠 수도 있다. 수평 방향 또는 수직 방향으로 이 삼각형들을 자를 때, 잘리는 삼각형의 개수를 구하는 프로그램을 작성하여라. 

어떤 삼각형이 잘린다는 것은, 삼각형이 자르는 직선을 기준으로 두 영역으로 나뉜다는 것을 말한다.


입력

입력 파일의 이름은 INPUT.TXT로 한다. 첫 번째 줄에는 삼각형의 수 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 이하이다.


출력

출력 파일의 이름은 OUTPUT.TXT로 한다. 각 시도에 대하여, 잘리는 삼각형의 수를 출력한다.


예제1

입력
3

100222

133540

544544

4

x=4

x=1

y=3

y=1
출력
0

1

1

2

예제2

입력
4

276005

717101111

5102968

19101041

4

y=6

x=2

x=4

x=9
출력
3

2

3

2

출처

COCI 2012/2013 - Contest 6

역링크