시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 79 29 26 48.148%

문제

시논은 GGO(건 게일 온라인)에서 유명한 저격수이다. 그녀는 오늘도 BoG(Bullets of GSHS)를 위해 연습에 매진하고 있다.

이번 연습은 그녀의 새로운 무기인 '핵카테'에 익숙해지기 위함이다.

핵카테는 기존 헤카테에 비해 관통력이 크게 높아진 총으로, 총을 쏜 방향으로 나아간 반직선 상의 여러명을 한 번에 맞추는 게 가능한 총이다.

시논은 좋아하는 저격 장소가 2개 있다. 시논은 이 2개의 장소에서만 저격을 하며, 지금은 첫번째 저격 장소에 위치해 있다. 

그녀는 새틀라이트 스캔을 통해 적들의 좌표를 알고 있으며, 가능한 적은 수의 총알로 적들을 모두 무찌르려고 한다.

또한, 동일한 총알 수로 모든 적을 맞출 수 있다면 장소를 옮기는 횟수가 가능한 최소가 되도록 하려고 한다.

시논을 도와 모든 적을 맞추는데 필요한 최소한의 총알 수와 장소 이동 횟수를 구해보자.

두 저격 장소의 위치는 서로 다르다는 것이 보장되며, 저격 장소가 적의 위치와 겹치는 경우는 존재하지 않는다. 하지만, 한 위치에 여러 명의 적이 있을 수 있다. 

입력

첫번째 줄에는 적의 수 $N$ ($1 \le N \le 20$)이 주어진다. 

그 후, $N$개의 줄에 걸쳐서 $xy$ 평면 위에 각 적이 위치한 좌표 $x_{enemy_i}, y_{enemy_i}$가 주어진다. ($-10^9 \le x_{enemy_i}, y_{enemy_i} \le 10^9$)

그 뒤에, 두 줄에 걸쳐서 시논이 좋아하는 두 저격 장소가 위치한 좌표 $x_{sinon_i}, y_{sinon_i}$가 주어진다. ($-10^9 \le x_{sinon_i} , y_{sinon_i} \le 10^9$)

단, 시논이 좋아하는 두 저격 장소의 좌표 중 먼저 입력되는 좌표가 시논이 현재 위치한 저격 장소의 좌표이다. 

출력

필요한 총알 수의 최솟값과 이때 장소 이동 횟수의 최소값을 공백을 사이에 두고 한 줄에 출력한다.

예제 입력 1

2
1 2
2 4
0 0
1 0

예제 출력 1

1 0

예제 입력 2

4
1 2
2 4
2 14
1 9
0 0
0 4

예제 출력 2

2 1

예제 입력 3

2
1 0
-1 0
0 0
3 0

예제 출력 3

1 1