[MINASTIRITH] 문제 😭😊😭😊😒
프단 한 번도 함락된 적이 없다는 성채도시 미나스 아노르에는 반지름이 8 킬로미터나 되는 거대한 원형 성벽, 람마스 에코르가 있습니다. 도시 전체를 감싸는 이 거대한 성벽에는 n 개의 초소가 배치되어 있습니다. 각 초소들은 해당 위치를 중심으로 반지름 ri 의 원 내부를 감시할 수 있는데, 성벽의 구조 때문에 초소는 불규칙하게 배치되어 있고 초소마다 감시할 수 있는 범위도 모두 다릅니다.
위 그림에서 굵은 실선은 성벽, 별은 초소의 위치, 그리고 점선은 각 초소가 감시할 수 있는 영역을 나타냅니다. 최소의 인원으로 성벽의 모든 부분을 감시하기 위해, 일부 초소에만 병사를 배치하려고 합니다. 각 초소의 위치와 감시 범위가 주어질 때, 성벽의 모든 부분을 감시하기 위해 필요한 최소한의 병사 수를 계산하는 프로그램을 작성하세요.
문제를 간단하게 하기 위해 성벽은 두께가 없는 원이고 초소는 점이라고 가정합니다.
[풀이]
문제를 읽어보시면 한번에 기하 문제인 것을 알 수 있습니다. 하지만 이 문제를 풀기위해 가능한 최대로 간단한 문제를 만드는 방식으로 접근하겠습니다.
먼저 원의 호를 표현 하는 방법으로 “초소를 감시할 수 있는 구간을 호로 갖는 부채꼴의 중심각을 [begin, end] 형태의 폐구간으로 표현”.
begin과 end를 구하기 위해 그림에서 loc은 x축의 양의 방향과 초소의 방향 사이의 각도이고,
range는 초소에서 감시할 수 있는 범위를 나타내게 됩니다.
따라서 begin과 end는 loc(+-) range로 구할 수 있습니다.
loc는 atan2함수로 쉽게 구할 수 있습니다. loc=atan2(y,x);
lange는 2\(\Theta\) 로 다음과 같은 아크사인 공식을 이용해 구할 수 있습니다.
\(\Theta\) = 2asin(r/2 * 1/8.0) 으로 구할 수 있습니다. (r = 8)
따라서 range = 2 * asin(r/16.0) 으로 나타낼 수 있습니다.
이제 [0,2\(\pi\)] 을 모두 덮을지 begin 과 end 로 알아 내면 됩니다. 이떄 위에서 사용한 atan 함수는 [-\(\pi\),\(\pi\)] 의 범위를 리턴하기 때문 이것을 fmod를 사용해 [0,2\(\pi\)] 구간으로 강제로 바꿔 줍니다. 하지만 0을 기준으로 품고 있는지 없는지를 판단하기 위해 range는 fmod를 사용하지 않는다.
convertToRange() 함수에서 구현
위에서 적절한 원을 기준으로하는 범위로 ranges에 저장하였다. 이를 쉽게 해결하기위해 선형으로 다음처럼생각하자.
이부분에서 처음 0을 덮는 범위를 선택하여 오른쪽으로 가장 긴 것을 선택한다.
이후 다시 그 가장 긴 오른쪽을 범위로 그것을 포함하는 오른쪽이 가장 긴 문제를 선택한다.
이것을 반복하여 최소한의 수로 모든 범위를 덮는 경우의 수를 구한다.
solveCircular(), solveLinear() 에서 구현.
입력
입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 초소의 개수 n (1 <= n <= 100) 이 주어지며, 그 후 n 줄에 각 3 개의 실수로 각 초소의 위치 yi, xi, 그리고 감시 범위 ri (0 < ri <= 16.001) 가 주어집니다.
성벽은 (0,0) 을 중심으로 하는 반지름 8 인 원으로, 모든 초소는 이 성벽 위에 위치합니다.
출력
각 테스트 케이스마다 한 줄에 필요한 최소의 병사 위치를 출력합니다. 만약 어떻게 하더라도 성벽의 모든 부분을 감시할 수 없다면 IMPOSSIBLE 을 대신 출력합니다. 입력에 주어지는 초소의 좌표, 혹은 감시 범위가 최대 0.0000001 만큼 변하더라도 답은 변하지 않는다고 가정해도 좋습니다.
입력 예제
3
10
7.02066050 -3.83540431 4.0
-7.23257714 -3.41903904 2.0
0.00000000 -8.00000000 8.0
-8.00000000 -0.00000000 4.8
-6.47213595 4.70228202 3.2
-4.70228202 6.47213595 4.8
7.60845213 -2.47213595 1.6
-2.47213595 -7.60845213 8.8
6.47213595 4.70228202 7.6
-0.00000000 8.00000000 4.8
4
8.00000000 0.00000000 8.00
0.00000000 -8.00000000 8.00
-8.00000000 -0.00000000 8.00
1.25147572 7.90150672 5.40
1
8 0 15.99
출력 예제
5
4
IMPOSSIBLE
전체 코드는 다음과 같습니다.
//
// MINASTIRITH.cpp
// AALGGO
//
// Created by inhyeok on 2021/10/20.
//
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
using namespace std;
ifstream fin("MINASTIRITH.txt");
int N; // 초소 개수
const double pi = 2.0 * acos(0); // acos(0) -> pi/2;
double x[100];
double y[100];
double r[100];
pair<double, double> ranges[100];
const int INF = 987654321;
int solveLinear(double begin, double end){
int used =0 , idx =0;
// 덮지 못한 선분이 남아 있는 동안 계속 함.
while(begin < end){
double maxCover = -1;
// begin 을 포함 하는 것중 가장 긴 것을 선택.
while(idx < N && ranges[idx].first <= begin){
maxCover = max(maxCover, ranges[idx].second);
idx++;
}
if(maxCover <= begin) return INF;
begin = maxCover;
used++;
}
return used;
}
int solveCircular(){
int ret = INF; // 엄청 큰 값 시작으로 대입.
for(int i=0; i<N; i++){
if(ranges[i].first <= 0 || ranges[i].second >= 2*pi){
// 0 을 덮는 구간을 선택
double begin = fmod(ranges[i].second, 2*pi);
double end = fmod(ranges[i].first+2*pi, 2*pi);
// [begin, end] 를 덮는 구간을 구한다.
ret = min(ret, 1+ solveLinear(begin,end));
}
}
return ret;
}
void convertToRange(){
for(int i=0; i< N; i++){
double loc = fmod(2*pi + atan2(y[i], x[i]), 2*pi); // [0,2pi] 구간으로 변경
double range = 2.0 * asin(r[i]/16.0);
ranges[i] = make_pair(loc-range, loc+range);
}
sort(ranges, ranges+N);
}
int main(int argc, const char * argv[]) {
int test_case;
fin >> test_case;
for(int Test = 0; Test < test_case; Test++){
fin >> N;
for(int i =0 ; i< N; i++){
fin >> y[i] >> x[i] >> r[i];
}
convertToRange();
if(solveCircular() == INF){
cout << "IMPOSSIBLE" << endl;
}
else cout << solveCircular() << endl;
}
return 0;
}
Comments