[BOJ 14266] 나는 가르친다 스위핑을

View as PDF

Submit solution

Points: 3
Time limit: 2.0s
Memory limit: 512M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

영선이는 BOJ 캠프의 강사다. 이번에 스위핑에 대한 세미나를 진행하였는데, 그 연습문제를 만들었다. “1사분면 정수 좌표계에 n개의 점이 주어질 때, 원점을 지나는 직선 중 직선위의 점들이 최대가 되는 직선에 대해, 그 점들의 개수를 구하여라”라 문제를 만들었지만, 나중에 보니 스위핑이 아닌 단순히 기울기로 만들어 개수를 세는 풀이의 허점이 존재하였다.</p>

영선이는 스위핑으로 풀게 하기 위하여 급하게 점을 선분으로 문제를 바꾸었다. 따라서 수강생인 당신은 바뀐 문제를 풀면 된다.

“1사분면 정수 좌표계에 n개의 선분이 주어질 때, 원점을 지나는 직선 중 직선이 교차하는 선분이 최대가 되는 직선에 대해, 그 선분들의 개수를 구하여라”

입력 형식

첫째 줄에는 선분의 개수 n이 주어진다.(1≤n≤100,000)</p>

다음 n줄에는 선분의 두 점 좌표 x1, y1, x2, y2가 주어진다.(1≤x1, y1, x2, y2≤1,000,000,000) 선분의 두 점의 같은 경우는 없으며, 선분끼리 교차할 수도 있다.

출력 형식

교차하는 선분이 최대가 되는 직선에 대해, 그 선분들의 개수를 구하시오.

예제 입력

3
4 4 8 2
5 5 6 6
7 7 2 6

예제 출력

3

Comments

There are no comments at the moment.