1870번 - 지붕 제작 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 9 | 2 | 2 | 33.333% |
문제
동원이는 지붕을 제작하는 한 건축가이다. 그리고 민균이는 지붕을 디자인하는 디자이너이다. 동원이는 민균이가 제작한 지붕의 디자인을 받아 지붕을 만들려 한다.
그런데 민균이가 제작한 디자인은 미적 효과에만 치중하였기 때문에 볼록다각형의 모양이 아니다. 그렇게 되면 비가 오거나 눈이 오면 밑으로 흘러내리지 않는 문제점이 생기게 된다. 그래서 동원이는 민균이가 준 지붕의 디자인을 조금 개선하여 볼록다각형 모양으로 지붕을 새로 만들려 한다.
민균이는 지붕을 디자인할 때 몇 개의 점을 가지고 디자인 하였다. 동원이는 이 점들을 가지고 다시 디자인을 하는데 제약 조건이 있다. 먼저 민균이가 디자인한 점은 모두 지붕의 아래에 있어야 한다. 그리고 지붕의 변의 개수는 K개 이하가 되어야 한다.
당신이 하여야 할 일은 다음과 같다. 동원이가 새로 디자인 한 지붕이 민균이가 디자인 한 것과 너무 많이 차이가 나면 민균이가 불만이 많기 때문에 차이를 최소로 하려 한다. 단, 디자인의 차이는 아래 그림으로 설명을 할 것이다.
K=2이며 위의 그림이 민균이가 한 디자인이고 밑에 두 그림이 동원이가 새로 디자인한 그림이라고 하자. 여기서 동원이가 만든 지붕과 민균이가 디자인한 지붕의 차이는 그림의 max를 의미한다. 즉 민균이가 만든 점에서 동원이가 디자인한 지붕과의 세로축 차이 중 최댓값을 의미한다는 말이다.
민균이가 디자인한 점들과 K가 주어져 있을 때, 동원이가 디자인한 지붕과 민균이가 디자인한 지붕과의 차이의 최솟값을 구하는 프로그램을 작성하여라.
입력
첫째 줄에 점의 개수 N과 변의 개수 k (1≤N≤100, 1≤k≤N) 가 주어진다. 그리고 두 번째 줄부터 N+1번째 줄까지 N개의 줄에 걸쳐서 점의 좌표 (x,y)가 주어진다. 단, x와 y는 0부터 10000 사이의 소수이다.
출력
첫째 줄에 최소 차이를 출력한다.
예제 입력 1
6 2 0.0 0.0 1.0 3.0 3.0 6.0 6.0 9.0 8.0 10.0 17.0 12.0
예제 출력 1
1.500
출처
ICPC > Regionals > North America > East Central North America Regional > 2006 East Central Regional Contest F번
- 문제를 번역한 사람: author10
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호