코인 슬라이더

시간 제한2초메모리 제한512 MB

요약

최대 16개의 동전 중에서 옮길 부분집합과 이동 순서를 정해, 움직이는 동전이 정지한 동전이나 이미 옮긴 동전과 충돌하지 않도록 하는 최대 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 비트 연산, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

동전 퍼즐을 푼다. 규칙은 다음과 같다.

탁자 위에 동전 $N$ 개가 놓여 있다. $i$ 번째 동전은 반지름이 $r_i$ 인 원이고, 처음에는 중심이 $(sx_i, sy_i)$ 에 있다. 각 동전에는 목표 위치가 하나씩 있다. $i$ 번째 동전은 중심이 $(tx_i, ty_i)$ 에 오도록 옮겨야 한다. 동전은 한 번에 하나씩 옮기고, 각 동전은 최대 한 번만 옮길 수 있다. 동전을 옮길 때는 처음 위치에서 목표 위치까지 직선을 따라 이동해야 한다. 또한 이동하는 도중을 포함해서 동전끼리 충돌해서는 안 된다.

퍼즐의 점수는 처음 위치에서 목표 위치로 옮긴 동전의 개수이다. 주어진 퍼즐에서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

N
r1 sx1 sy1 tx1 ty1
.
.
.
rN sxN syN txN tyN

첫째 줄에 퍼즐에 쓰이는 동전의 개수 $N$ ( $1 \le N \le 16$ )이 주어진다. 이어지는 $N$ 개 줄 중 $i$ 번째 줄에는 정수 다섯 개 $r_i$ , $sx_i$ , $sy_i$ , $tx_i$ , $ty_i$ ( $1 \le r_i \le 1{,}000$ , $-1{,}000 \le sx_i, sy_i, tx_i, ty_i \le 1{,}000$ , $(sx_i, sy_i) \ne (tx_i, ty_i)$ )가 주어진다. $r_i$ 는 $i$ 번째 동전의 반지름, $(sx_i, sy_i)$ 는 처음 위치, $(tx_i, ty_i)$ 는 목표 위치이다.

처음 위치에서 동전끼리 맞닿거나 겹치는 일은 없다. 또한 각 동전의 반지름이 $10^{-5}$ 만큼 달라져도 최대 점수는 바뀌지 않는다.

출력

주어진 퍼즐의 최대 점수를 한 줄에 출력한다.

힌트

첫 번째 예제에서 세 번째 동전은 나머지 두 동전에 막혀 옮길 수 없다.

예제 1. 처음 위치

예제 1. 이동 후

예제3

예제 1
입력
```
3
2 0 0 1 0
2 0 5 1 5
4 1 -10 -5 10
```
예상 출력
```
2
```
예제 2
입력
```
3
1 0 0 5 0
1 0 5 0 0
1 5 5 0 5
```
예상 출력
```
3
```

예제 3

입력

예상 출력