사다리꼴 2초 128MB
문제
두 평행선에 N개의 사다리꼴이 있다. 각 사다리꼴은 위쪽 변이 첫 번째 평행선에 있고 아래쪽 변이 두 번째 평행선에 있는 형태이다.
각 사다리꼴의 위쪽 변은 좌표 ai와 좌표 bi를 연결하는 선분이며 아래쪽 변은 좌표 ci와 좌표 di를 연결하는 선분이다.
우리는 어떤 사다리꼴이 겹치지 않도록 사다리꼴을 뽑으려고 한다.
겹치지 않게 뽑을 수 있는 사다리꼴의 최대 개수와 그렇게 뽑는 경우의 수를 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 사다리꼴의 수 N이 주어진다.
다음 N개의 줄에는 사다리꼴의 좌표 ai, bi, ci, di가 주어진다.
두 사다리꼴은 한 점에서 만나지 않는다.
● 1 ≤ N ≤ 100,000
● 1 ≤ ai, bi, ci, di> ≤ 1,000,000,000
● 전체 데이터의 40%는 N ≤ 5,000이다.
출력
첫 번째 줄에 두 개의 답을 출력한다.
첫 번째 답은 뽑을 수 있는 사다리꼴의 최대 개수이다.
두 번째 답은 사다리꼴을 최대한으로 뽑는 가짓수를 30013으로 나눈 나머지이다.
예제
7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
3 8
로그인해야 코드를 작성할 수 있어요.