34404번 - 파티 홍보

문제

PIMM 파티를 준비 중인 영도는 대회 홍보를 위해 거리 곳곳에 현수막과 포스터를 설치했다. 각 홍보물은 직사각형 형태로, 건물의 벽면, 펜스, 창문 등을 피해 잘 보이도록 서로 겹치지 않게 배치되었다. 그러나 거리의 구조상 어떤 위치에서는 홍보물이 난간이나 창문 등에 가려 일부만 보이게 된다. 특히 가로로 긴 난간이나 창문 하나가 시야를 막고 있다면, 그 선을 기준으로 선 아래의 부분은 전혀 보이지 않게 된다. 사람들은 홍보물이든 포스터든, 전체 면적의 50ドル\%$ 이상이 보여야 그것을 인지할 수 있다고 한다. 따라서 영도는 특정한 시야를 기준으로 사람들이 인지할 수 있는 홍보물의 개수를 알고 싶어졌다.

영도는 이 문제를 단순화하여 다음과 같이 도식화했다.

1. 홍보물은 겹치지 않는 여러 개의 직사각형으로 표현된다. 각 직사각형은 왼쪽 아래 꼭짓점의 좌표 $(x,y)$와 오른쪽 위 꼭짓점의 좌표 $(p,q)$으로 주어진다. 모든 직사각형은 양의 면적을 가지며, 서로 겹치지 않는다.
2. 한 개의 직선이 사람의 시야를 가렸을 때, 이 선보다 아래에 위치한 면적은 모두 가려진다. 이때 직선은 $y = ax + b$의 형태로 표현되며, $y < ax + b$인 영역은 가려진다. 단, 직선은 각 직사각형의 중심을 지나지 않는다.
3. 이때, 50ドル\%$ 이상의 면적이 보이는 홍보물의 개수를 구한다.

직선과 각 홍보물의 형태가 주어질 때, 영도를 도와 인지할 수 있는 홍보물의 개수를 구해보자.

입력

첫 번째 줄에 홍보물의 개수 $N$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 직사각형의 정보를 나타내는 정수 $x_i,ドル $y_i,ドル $p_i,ドル $q_i$가 공백으로 구분되어 주어진다.

$N+2$번째 줄에 직선의 정보를 나타내는 정수 $a,ドル $b$가 공백으로 구분되어 주어진다.

출력

주어진 직선을 기준으로 50ドル\%$ 이상 면적이 드러나는 홍보물의 개수를 출력한다.

제한

• 1ドル \le N \le 1,000円$
• $-1,000円,000円 \le x_i < p_i \le 1,000円,000円$
• $-1,000円,000円 \le y_i < q_i \le 1,000円,000円$
• $-1,000円,000円 \le a,b \le 1,000円,000円$
• 입력으로 주어지는 모든 수는 정수이다.
• 모든 직사각형은 서로 겹치지 않는다.
• 직선은 각 직사각형의 중심을 지나지 않는다.

힌트