직사각형

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

요약
원점을 지나는 직선이 최대한 많은 사각형과 만나도록, 각 사각형이 원점에서 보이는 각도 구간을 이용해 최적의 직선을 찾는 문제입니다.
난이도

보통10점 중 6점

유형
구간, 정렬, 기하
정답자
아직 제출이 없습니다

문제

2차원 평면에 N개의 직사각형이 주어진다. 모든 직사각형의 변은 좌표축과 평행하고, 각 꼭짓점의 좌표는 자연수이다. 직사각형들은 서로 겹치거나 완전히 일치할 수 있으며, 어떤 직사각형이 다른 직사각형 안에 들어 있을 수도 있다.

원점 (0, 0)을 지나는 직선을 하나 그린다. 이 직선이 직사각형의 내부나 변과 만나면 그 직사각형과 교차한다고 본다. 직선이 꼭짓점 하나만 지나가는 경우도 교차한 것으로 간주한다.

원점을 지나는 직선을 적절히 선택했을 때, 동시에 교차할 수 있는 직사각형의 최대 개수를 구하시오.

입력

첫째 줄에 직사각형의 개수 N (1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점 좌표 xbl, ybl 및 오른쪽 위 꼭짓점 좌표 xtr, ytr가 공백으로 구분되어 주어진다.

모든 좌표는 1,000,000,000 이하의 자연수이며 xbl < xtr, ybl < ytr를 만족한다.

출력

첫째 줄에 원점을 지나는 한 직선이 교차할 수 있는 직사각형 개수의 최댓값을 출력한다.

예제1

  1. 예제 1

    입력
    8
1 8 7 11
18 10 20 12
17 1 19 7
12 2 16 3
16 7 19 9
8 4 12 11
7 4 9 6
10 5 11 6
    예상 출력
    5