아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

실 전화기

면접 대비

시간 제한1초메모리 제한128 MB

요약
두 창문을 잇는 선분과 만나거나 닿는 다각형 건물의 개수를 센다. 꼭짓점이나 변에 닿아도 시야가 가려진 것으로 본다.
난이도

보통10점 중 6점

유형
기하, 구현, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

로미(Romy)와 줄스(Jules)는 휴대폰으로 서로 이야기를 나누곤 했습니다. 그런데 두 사람의 부모님은 사이가 좋지 않아 둘이 더는 통화하지 못하게 하기로 했고, 급기야 휴대폰까지 빼앗아 버렸습니다. 그래서 로미와 줄스는 다른 방법으로 연락해야 합니다. 인터넷에서 아이디어를 찾던 두 사람은 "실 전화기"를 만들기로 했습니다.

실 전화기는 빈 깡통 두 개를 실로 연결한 간단한 장치입니다. 사용할 때는 실을 팽팽하게 당긴 뒤 한 사람이 말하고 다른 사람이 듣습니다. 실이 진동하며 한쪽 깡통에서 다른 쪽 깡통으로 소리를 전달해야 하므로, 실에는 아무것도 닿아서는 안 됩니다.

실 전화기를 설치하려면 두 사람의 방 창문 사이에 막힘없는 시야(직선 경로)가 필요합니다. 방과 방 사이에 실을 이을 수 있는지 확인하기 위해 두 사람은 모든 것을 정수 좌표로 나타낸 지도에 표시했습니다. 아래 세 가지 상황을 생각해 봅시다.

그림에서 "Romy"는 좌표 (0,0)(0, 0)에 있는 로미의 창문이고, "Jules"는 좌표 (3,3)(3, 3)에 있는 줄스의 창문입니다. 첫 번째 그림에서는 두 창문 사이에 건물이 있어 시야를 가립니다. 두 번째 그림에서는 건물이 시야를 가리지 않아 실 전화기를 설치할 수 있습니다. 세 번째 그림에서는 로미의 창문에서 줄스의 창문으로 그은 직선이 건물의 모서리에 닿습니다. 실은 아무것도 닿아서는 안 되므로, 이 경우 시야가 가려진 것으로 보고 실 전화기를 설치할 수 없습니다.

입력

첫째 줄에 네 정수 xR yR xJ yJx_R\ y_R\ x_J\ y_J가 주어집니다. 로미의 창문은 (xR,yR)(x_R, y_R), 줄스의 창문은 (xJ,yJ)(x_J, y_J)이며, −1000≤xR,xJ≤1000-1000 \le x_R, x_J \le 1000, −1000≤yR,yJ≤1000-1000 \le y_R, y_J \le 1000입니다.

둘째 줄에는 건물의 개수를 나타내는 정수 nn (0≤n≤1000 \le n \le 100)이 주어집니다. 이어지는 nn개의 줄에는 각각 건물 하나가 주어지는데, 먼저 그 건물의 모서리(꼭짓점) 개수를 나타내는 정수가 오고, 그 뒤에 각 모서리의 정수 좌표가 시계 방향 또는 반시계 방향 순서로 나열됩니다. 어떤 건물도 모서리를 3232개보다 많이 가지지 않습니다.

출력

두 창문 사이의 시야에 닿거나 시야를 가리는 건물의 개수를 정수 하나로 출력합니다.

예제4

  1. 예제 1

    입력
    0 0 3 3
    1
    4 1 2 2 2 2 1 1 1
    
    예상 출력
    1
    
  2. 예제 2

    입력
    0 0 3 3
    0
    
    예상 출력
    0
    
  3. 예제 3

    입력
    0 0 4 0
    1
    4 1 -1 3 -1 3 1 1 1
    
    예상 출력
    1
    
  4. 예제 4

    입력
    0 0 4 0
    1
    4 1 2 3 2 3 4 1 4
    
    예상 출력
    0