시간 제한
메모리 제한
시간 제한
2초
메모리 제한
128 MB
2차원 평면에 N개의 직사각형이 주어진다. 모든 직사각형의 변은 좌표축과 평행하고, 각 꼭짓점의 좌표는 자연수이다. 직사각형들은 서로 겹치거나 완전히 일치할 수 있으며, 어떤 직사각형이 다른 직사각형 안에 들어 있을 수도 있다.
원점 (0, 0)을 지나는 직선을 하나 그린다. 이 직선이 직사각형의 내부나 변과 만나면 그 직사각형과 교차한다고 본다. 직선이 꼭짓점 하나만 지나가는 경우도 교차한 것으로 간주한다.
원점을 지나는 직선을 적절히 선택했을 때, 동시에 교차할 수 있는 직사각형의 최대 개수를 구하시오.
첫째 줄에 직사각형의 개수 N (1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 직사각형의 왼쪽 아래 꼭짓점 좌표 xbl, ybl 및 오른쪽 위 꼭짓점 좌표 xtr, ytr가 공백으로 구분되어 주어진다.
모든 좌표는 1,000,000,000 이하의 자연수이며 xbl < xtr, ybl < ytr를 만족한다.
첫째 줄에 원점을 지나는 한 직선이 교차할 수 있는 직사각형 개수의 최댓값을 출력한다.