1129 : 평면내 선분의 교점
제한시간: 1000 ms
메모리제한: 128 MB
해결횟수: 301 회
시도횟수: 758 회
좌표평면에서 두 개의 점이 주어지면 하나의 선분을 표현할 수 있다.
또한 선분이 두 개 이상이 존재한다면 이 선분들은 서로 만날 가능성이 생긴다. 이렇게 선분이 서로 만나는 점을 교점이라고 한다.
그림으로 표현하면 다음과 같다.
N개의 선분을 입력받고 몇 개의 교점이 생기는지 알아보는 프로그램을 작성하라.
만약 중복되는 교점이 생기는 경우 각각의 교점으로 인정하며,
주어진 선분들 중에 기울기가 같은 선분들끼리 겹치는 경우는 없다.
또한 완전히 교차되는 점 만을 교점으로 본다.
첫 번째 줄에 숫자 N을 입력 받는다. (2≤N≤20) 두 번째 줄부터 두 개의 점을 한 줄씩 입력받는다. 네 개의 숫자를 차례로 입력받아 각각 (x1, y1), (x2, y2) 에 대입한다. N번 반복해서 입력받는다. 모든 좌표는 50이하 음이 아닌 정수이다.
교점의 개수만 출력한다.
2 3 5 4 1 5 5 1 2 |
1 |
출처 : 경기도 정보올림피아드 알고리즘