시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB74222010321.548%

문제

주어진 $N$개의 선분 중 중복을 허용하여 두 개를 고르는 모든 경우에 대해, 두 선분이 다음 중 어떤 관계인지 구하는 프로그램을 작성하시오.

  • 0: 교점이 없음
  • 1: 교점이 정확히 하나 있으며, 그 교점이 적어도 한 선분의 끝점임
  • 2: 교점이 정확히 하나 있으며, 그 교점이 어느 선분의 끝점도 아님
  • 3: 교점이 무한히 많이 있음

입력

첫 줄에 $N$이 주어진다. ($1 \leq N \leq 2\,000$)

그 다음 줄부터 한 줄에 한 선분씩, 한 끝점의 $x$ 좌표와 $y$ 좌표, 그리고 다른 끝점의 $x$ 좌표와 $y$ 좌표가 주어진다. 모든 좌표는 정수이고 $-10^9$ 이상 $10^9$ 이하이다. 길이가 $0$인 선분은 없다.

출력

한 줄에 숫자 $N$개씩 공백 없이 총 $N$줄 출력한다. $i$번째 줄의 $j$번째 숫자는 $i$번째와 $j$번째 선분의 관계를 나타내는 숫자이다.

예제 입력 1

4
-2 -1 0 2
0 2 2 -1
-2 -1 2 -1
-2 0 2 0

예제 출력 1

3112
1312
1130
2203

예제 입력 2

6
0 0 1 1
1 1 2 2
2 2 3 3
0 0 2 2
1 1 3 3
0 0 3 3

예제 출력 2

310313
131333
013133
331333
133333
333333

출처