반응형
https://www.acmicpc.net/problem/17371
17371번: 이사
$(\frac{2}{3}, \frac{1}{3})$으로 이사를 가면 가장 가까운 편의시설은 (0, 1)으로 거리는 $\frac{2\sqrt{2}}{3}$이고, 가장 먼 편의시설은 (-4, 1) 혹은 (4, -3)으로 거리는 둘 다 $\frac{10\sqrt{2}}{3}$이다. 두 거리의
www.acmicpc.net
[ 문제풀이 ]
생각을 조금만 해보면 쉽게 풀 수 있는 문제입니다.
점들 중 하나를 골라 다른 점들과 거리를 비교했을 때 가장 가까운 점은 거리가 0, 가장 먼 거리가 d일 때 평균 거리는 $ \frac{d}{2}$입니다. 따라서 이들 중 가장 짧은 거리를 구해주면 됩니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<iostream> #include<cmath> using namespace std; int N; struct pos { int x; int y; }; pos arr[1000]; int ans; int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> arr[i].x >> arr[i].y; } double minDist = 9999999; for (int i = 0; i < N; i++) { int x = 0; int y = 0; double maxDist = 0; for (int j = 0; j < N; j++) { //i번째 점부터 j번째 점까지 거리 중 가장 먼 거리를 maxDist에 저장 double dist = sqrt(pow(arr[i].x - arr[j].x, 2) + pow(arr[i].y - arr[j].y, 2)); maxDist = max(maxDist, dist); } if (minDist > maxDist) { //maxDist 중 가장 짧은 거리를 minDist에 저장하고 idx를 ans에 저장 ans = i; minDist = maxDist; } } cout << arr[ans].x << " " << arr[ans].y; } | cs |
반응형
'백준' 카테고리의 다른 글
[ 백준 ] 1708번 - 볼록 껍질 (C++) (0) | 2022.07.17 |
---|---|
[ 백준 ] 1086번 - 박성원 (C++) (0) | 2022.07.15 |
[ 백준 ] 14428번 - 수열과 쿼리 16 (C++) (0) | 2022.07.13 |
[ 백준 ] 13977번 - 이항 계수와 쿼리 (C++) (0) | 2022.07.12 |
[ 백준 ] 11689번 - GCD(n, k) = 1 (C++) (0) | 2022.07.11 |