시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 272 | 125 | 103 | 48.815% |
상근 바게트에서 삼각 페스트리 N개를 구웠다. 모든 페스트리는 2차원 평면 위에서 정수 좌표 꼭짓점을 가지는 삼각형으로 나타낼 수 있다.
상근이의 말썽꾸러기 아들 정인이는 커다란 칼을 들고 페스트리를 자르려고 한다. 정인이는 좌표평면에서 수직 방향(x = c)이나 수평 방향(y = c)으로 칼질을 한다. 정인이가 칼질을 할 때, 총 몇 개의 페스트리가 잘리는지 구하려고 한다. 페스트리가 칼질로 두 부분으로 나누어졌을 때, 두 부분의 넓이가 0보다 크면 잘린 것이다.
페스트리의 위치와 정인이의 칼질이 주어졌을 때, 몇 개의 페스트리가 잘리는지 구하는 프로그램을 작성하시오.
첫째 줄에 페스트리의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)
다음 N개 줄에는 106보다 작은 음이 아닌 정수 여섯 개가 주어진다. 정수는 순서대로 (x1, y1), (x2, y2), (x3, y3)이며, 삼각 페스트리를 이루는 세 꼭짓점이다. 세 점은 일직선 위에 있지 않다. 또, 페스트리는 겹치거나 접할 수도 있다.
다음 줄에는 정인이의 칼질의 수 M이 주어진다. (2 ≤ M ≤ 100 000)
다음 M개 줄에는 정인이가 어떻게 칼질을 하려고 하는지가 주어진다. 방정식 "x = c" 또는 "y = c"와 같은 형식으로 주어지며, c는 106보다 작은 음이 아닌 정수이다.
첫째 줄에 입력으로 주어지는 정인이의 칼질이 페스트리 몇 개를 자르는지 출력한다. 모든 칼질은 독립적으로 생각하면 된다. 즉, 칼질을 하고 난 다음 페스트리가 마법처럼 붙는다고 생각하면 된다.
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
Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #6 4번