문제
시논은 KGO(KOI 건 게일 온라인)에서 유명한 저격수이다.
그녀는 오늘도 BoK(Bullets of KOI)를 위해 연습에 매진하고 있다.
이번 연습은 시논의 새로운 무기인 '핵카테'에 익숙해지기 위함이다.
핵카테는 기존 헤카테에 비해 관통력이 크게 높아진 총으로,
한 발로 직선 상의 여러명을 한 번에 맞추는 것도 가능해진 총이다.
시논은 좋아하는 저격 장소가 2개 있다.
시논은 2개의 장소에서만 저격을 하며, 시논은 지금 첫번째 저격 장소에 위치해 있다.
그녀는 새틀라이트 스캔을 통해 적들의 좌표를 알고 있으며, 최대한 적은 총알로 적들을 모두 섬멸하려 한다.
또한, 동일한 총알 수로 저격할 수 있다면 최대한 장소의 옮기는 횟수를 줄이려고 한다.
시논을 도와 모든 적을 맞추는데 필요한 최소한의 총알 수와 장소 이동 횟수를 구해보자.
[부분 점수 조건]
1) N≤10 (50%)
2) 제약조건 없음(50%)
입력
첫번째 줄에는 적의 수 N(1<=N<=20)이 주어진다.
2번째~(N+1)번째 줄에는 적들의 위치가 2차원 평면으로 (xi, yi)처럼 공백을 사이로 주어진다.
(-109 < i,yi < 109) 그 뒤에 시논이 좋아하는 저격 장소가 (xj, yj)처럼 공백을 사이로 주어진다. (-109 < xi,yi < 10<9)
출력
필요한 총알 수와 장소 이동 횟수의 최소값을 공백을 사이에 두고 출력한다.
예제 #1
2
1 2
2 4
0 0
1 0
1 0
예제 #2
4
1 2
2 4
2 14
1 9
0 0
0 4
2 1
예제 #3
2
1 0
-1 0
0 0
3 0
1 1
출처
william202
로그인해야 코드를 작성할 수 있어요.