[백준/python] 15821번 낚이고 낚아라

https://www.acmicpc.net/problem/15821

15821번: 낚이고 낚아라

좌표 평면에 다각형 모양의 낚시터가 여러개 있다. (그 다각형의 좌표는 모두 입력으로 주어진다.)

n개의 낚시터 중 최소 k개의 낚시터가 원점(0,0)에서 도달 가능하게 하기 위한 낚싯대의 최소 길이를 구하는 문제이다.

원점과 낚시터 한 곳의 관계를 생각해봤을 때, 그 다각형 영역에 모두 닿을 수 있으려면 낚시대의 길이는 최소 원점에서 가장 먼 꼭짓점과의 거리와 같아야 한다.

때문에, 두 점사이의 거리 공식을 사용하면 된다. 실제 거리를 구하려면 a^2+b^2에 루트를 씌워야 하지만, 출력이 제곱 형식이므로 변형시키지 않는다.

여러 개의 (x,y)가 한 줄로 입력되므로, 이에 유의해서 for문을 작성해야 한다.

한 다각형의 모든 꼭짓점 중 원점에서 가장 거리가 먼 점과의 거리를 max로 설정하고 리스트에 삽입한다.

반복문을 모두 끝내면, ans에는 낚시터별 가장 먼 거리가 저장된다.

오름차순으로 정렬하고, k에 맞게 출력해주면 된다.