티스토리 뷰
요즘 기하를 많이 풀고 있어서 기하에 관한 글도 좀 적어보려고 한다. 기하도 생각보다 복잡한 트릭이나 기술이 많이 쓰였고 특히 최근에 ICPC 서울 리저널 문제 셋을 돌아봤는데 어려운 기하 문제도 종종 나왔었다. 그래서 기하도 좀 열심히 풀어보려 한다.
13433번: 기하 문제
첫째 줄에 가장 왼쪽 원과 직선이 닿는 점과 가장 오른쪽 원과 직선이 닿는 점 사이의 거리의 최솟값을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.
www.acmicpc.net
원을 직선에 접하도록 겹치지 않게 나열하라는 문제이다.
이런 간단한 기하적 아이디어가 금방 떠올랐고, 실수 오차도 float로 감당할 만한 수준인것 같아서 구현을 해봤지만 예제에서 바로 저 아이디어만으로는 풀 수 없다는 걸 깨달았다.
이런 경우가 있을 수 있다. 반지름이 최대 10억이니 충분히 사이에 원이 한개 혹은 매우 많은 원이 들어갈 수 있다. 그래서 누적합 하듯이 기록을 남겨가면서 원 사이에 들어가 길이가 씹히는 경우를 걸러주었다.
한번 틀렸는데 안일하게 $N \times \max R$을 최댓값으로 잡아서 그랬다. 항상 초기화는 넉넉하게 하자.
'코딩일지' 카테고리의 다른 글
| 백준 1028번 - 다이아몬드 광산 (1) | 2023.10.24 |
|---|---|
| 9월 일지 (0) | 2023.09.30 |
| 백준 그리디 일지 (3) (0) | 2023.04.29 |
| 백준 DP 일지 2 (0) | 2023.04.20 |
| 백준 그리디 일지 (2) - 순열 사이클 분할 (0) | 2023.04.05 |