COCI 2012/2013 - Contest 6- 삼각형 자르기 (BUREK) > 문제은행 : 정보올림피아드&알고리즘




1688 : 삼각형 자르기 (BUREK)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
9 회   
시도횟수
29 회   

문제

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로 한다.
각 시도에 대하여, 잘리는 삼각형의 수를 출력한다.


입력 예

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

출력 예

0
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

출력 예

3
2
3
2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP