[MINASTIRITH] 문제 😭😊😭😊😒Permalink
프단 한 번도 함락된 적이 없다는 성채도시 미나스 아노르에는 반지름이 8 킬로미터나 되는 거대한 원형 성벽, 람마스 에코르가 있습니다. 도시 전체를 감싸는 이 거대한 성벽에는 n 개의 초소가 배치되어 있습니다. 각 초소들은 해당 위치를 중심으로 반지름 ri 의 원 내부를 감시할 수 있는데, 성벽의 구조 때문에 초소는 불규칙하게 배치되어 있고 초소마다 감시할 수 있는 범위도 모두 다릅니다.
위 그림에서 굵은 실선은 성벽, 별은 초소의 위치, 그리고 점선은 각 초소가 감시할 수 있는 영역을 나타냅니다. 최소의 인원으로 성벽의 모든 부분을 감시하기 위해, 일부 초소에만 병사를 배치하려고 합니다. 각 초소의 위치와 감시 범위가 주어질 때, 성벽의 모든 부분을 감시하기 위해 필요한 최소한의 병사 수를 계산하는 프로그램을 작성하세요.
문제를 간단하게 하기 위해 성벽은 두께가 없는 원이고 초소는 점이라고 가정합니다.
[풀이]Permalink
문제를 읽어보시면 한번에 기하 문제인 것을 알 수 있습니다. 하지만 이 문제를 풀기위해 가능한 최대로 간단한 문제를 만드는 방식으로 접근하겠습니다.
먼저 원의 호를 표현 하는 방법으로 “초소를 감시할 수 있는 구간을 호로 갖는 부채꼴의 중심각을 [begin, end] 형태의 폐구간으로 표현”.
begin과 end를 구하기 위해 그림에서 loc은 x축의 양의 방향과 초소의 방향 사이의 각도이고,
range는 초소에서 감시할 수 있는 범위를 나타내게 됩니다.
따라서 begin과 end는 loc(+-) range로 구할 수 있습니다.
loc는 atan2함수로 쉽게 구할 수 있습니다. loc=atan2(y,x);
lange는 2
위에서 적절한 원을 기준으로하는 범위로 ranges에 저장하였다. 이를 쉽게 해결하기위해 선형으로 다음처럼생각하자.
이부분에서 처음 0을 덮는 범위를 선택하여 오른쪽으로 가장 긴 것을 선택한다.
이후 다시 그 가장 긴 오른쪽을 범위로 그것을 포함하는 오른쪽이 가장 긴 문제를 선택한다.
이것을 반복하여 최소한의 수로 모든 범위를 덮는 경우의 수를 구한다.
solveCircular(), solveLinear() 에서 구현.
입력Permalink
입력의 첫 줄에는 테스트 케이스의 수 c (c <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 초소의 개수 n (1 <= n <= 100) 이 주어지며, 그 후 n 줄에 각 3 개의 실수로 각 초소의 위치 yi, xi, 그리고 감시 범위 ri (0 < ri <= 16.001) 가 주어집니다.
성벽은 (0,0) 을 중심으로 하는 반지름 8 인 원으로, 모든 초소는 이 성벽 위에 위치합니다.
출력Permalink
각 테스트 케이스마다 한 줄에 필요한 최소의 병사 위치를 출력합니다. 만약 어떻게 하더라도 성벽의 모든 부분을 감시할 수 없다면 IMPOSSIBLE 을 대신 출력합니다. 입력에 주어지는 초소의 좌표, 혹은 감시 범위가 최대 0.0000001 만큼 변하더라도 답은 변하지 않는다고 가정해도 좋습니다.
입력 예제Permalink
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
출력 예제Permalink
5
4
IMPOSSIBLE
전체 코드는 다음과 같습니다.Permalink
//
// 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