[BOJ 14266] 나는 가르친다 스위핑을
View as PDF
Submit solution
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text
Points:
3
Time limit:
2.0s
Memory limit:
512M
Problem types
Allowed languages
영선이는 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