슈팅 연습

면접 대비

시간 제한1초메모리 제한1024 MB

요약
현재 커서에서 가장 먼 과녁을 골라 없애고 새 과녁을 추가하는 과정을 M번 반복하며 얻는 점수의 합을 구한다.
난이도

쉬움10점 중 3점

유형
시뮬레이션, 기하, 완전 탐색
정답자
아직 제출이 없습니다

문제

FPS 게임 실력을 향상시키고 싶은 정우는 과녁 맞추기 훈련을 진행 중이다. 이 훈련에서 컴퓨터 화면을 2차원 좌표 평면으로 정의하여 과녁의 위치를 죄표로 나타낼 수 있다. 화면에서 오른쪽 방향으로 이동할수록 xx 값이 증가하고 위쪽으로 이동할수록 yy 값이 증가한다.

초기 상태에서 마우스 커서는 항상 (0,0)(0, 0)에 위치하며, 컴퓨터 화면 위에는 NN개의 과녁이 있다. 마우스 커서를 특정 과녁으로 이동하여 클릭하면 해당 과녁이 사라지고 점수를 얻게 된다. 이때 얻는 점수는 이동하기 전 마우스 커서의 위치에서 특정 과녁의 위치까지의 거리를 제곱한 값이다. 여기서 거리는 유클리드 거리로, 두 점 사이의 직선 거리를 의미한다.

과녁을 하나 없애면 새로운 과녁이 화면에 나타난다. 정우는 각 이동에서 현재 마우스 커서에서 가장 멀리 떨어진 과녁을 맞추는 전략을 사용한다. 이 과정을 MM번 반복할 때, 정우가 얻는 총 점수를 구하자.

동일한 위치에 과녁이 나타나는 경우는 없으며, 각 이동 전에 마우스 커서에서 가장 먼 과녁은 항상 유일함이 보장된다.

입력

첫 번째 줄에 NN과 MM이 공백으로 구분되어 주어진다.(1≤N,M≤100)(1 \le N, M \le 100)

두 번째 줄부터 NN개의 줄에 걸쳐 현재 화면에 나타나 있는 과녁의 좌표를 나타내는 두 정수 x_i,y_ix\_i, y\_i가 공백으로 구분되어 주어진다. (−100≤x_i,y_i≤100)(-100 \le x\_i, y\_i \le 100)

다음 MM개의 줄에 걸쳐 다음에 나타날 과녁의 좌표를 나타내는 두 정수 x_j,y_jx\_j, y\_j가 차례대로 주어진다. (−100≤x_j,y_j≤100)(-100 \le x\_j, y\_j \le 100)

출력

정우가 얻는 총 점수를 출력한다.

예제1

  1. 예제 1

    입력
    2 3
    -1 0
    5 0
    1 2
    1 1
    6 2
    
    예상 출력
    69