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

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

같은 풍경

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

요약
x축 위 M개 지점에서 나무 N그루를 왼쪽에서 오른쪽으로 본 순서가 x축 아래 호영이의 시점과 같은 사진이 몇 장인지 센다.
난이도

보통10점 중 7점

유형
기하, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

호영이와 우진이는 넓은 2차원 평면에 살고 있다. 그 평면의 xx축 위쪽의 반평면에는 NN그루의 나무가 심어져 있다. 두 사람은 xx축의 양의 방향으로부터 반시계 방향으로 0∘0^{\circ}에서 180∘180^{\circ}까지 모든 풍경이 찍히게 파노라마 사진을 찍었다.

우진이는 xx축상의 총 MM개의 지점에서 사진을 찍었고, 호영이는 xx축 아래쪽의 반평면 어딘가에서 정확히 한 장을 찍었다. 각각의 나무는 번호가 매겨져 있는데, 두 사람은 왼쪽에서 오른쪽으로 나무가 보이는 순서가 같은 사진을 같은 풍경의 사진이라고 정의했다.

호영이가 사진을 찍은 위치와 우진이가 사진을 찍은 MM개의 위치가 전부 주어질 때, 우진이가 찍은 사진 중 호영이가 찍은 사진과 같은 풍경의 사진이 몇 장이나 있는지 알아보자.

단, 호영이가 찍은 사진에서 두 그루의 나무가 겹쳐 보이는 경우는 주어지지 않는다. 따라서 우진이가 찍은 사진에서 두 그루의 나무가 겹쳐 보인다면 호영이가 찍은 사진과 절대 같은 풍경이 될 수 없다.

입력

첫 번째 줄에 나무의 개수 NN과 우진이가 찍은 사진의 수 MM, 호영이가 사진을 찍은 위치의 x,yx, y좌표 X,YX, Y가 공백으로 구분되어 주어진다. (1≤N≤100,000;(1 \le N \le 100\\,000; 1≤M≤100,000;1 \le M \le 100\\,000; −109≤X≤109;-10^9 \le X \le 10^9; −109≤Y≤−1)-10^9 \le Y \le -1)

두 번째 줄부터 N+1N + 1번째 줄까지 1+i1 + i번째 줄에 ii번째 나무의 x,yx, y좌표를 나타내는 x_i,y_ix\_i, y\_i가 공백으로 구분되어 주어진다. (−109≤x_i≤109(-10^9 \le x\_i \le 10^9; 1≤y_i≤109)1 \le y\_i \le 10^9)

N+2N + 2번째 줄에 우진이가 사진을 찍은 위치의 xx좌표 MM개가 공백으로 구분되어 주어진다. (−109≤x≤109)(-10^9 \le x \le 10^9)

모든 좌표는 정수로 주어지며, 문제 설명에 따라 호영이의 위치에서 두 그루의 나무가 겹쳐 보이는 경우는 주어지지 않는다.

출력

우진이가 찍은 사진 중 호영이가 찍은 사진과 같은 풍경인 사진이 몇 장 있는지 구해서 첫째 줄에 출력한다.

예제1

  1. 예제 1

    입력
    3 3 1 -8
    1 1
    2 2
    3 1
    1 2 4
    
    예상 출력
    2