[탐욕법] [시도x] MINASTIRITH 미나스 아노르

1. 문제의 데이터를 변형해야한다.

 

초소의 실수 좌표들이 주어지고, 반지름이 주어진다.

 

이 데이터들을 가공하여 문제를 바로 푸는 것은 까다롭다.

 

그러므로 책에서는 이 데이터들을 중심각 구간으로 표현하였다.

 

중심각 이외에 원과 원이 만나는 X축 구간으로도 풀 수 있을것 같다.

 

2. 탐욕법

 

각 초소들의 구간으로 나타내면 이것은 활동 선택문제와 매우 유사하다.

 

하지만 이 문제는 처음 구간을 고르는게 중요하다.

 

원은 순환하기 때문에 처음 구간은 맨 마지막 구간과 이어지기 때문이다.

 

 

전체 구간이 0~2π 라고 할때

 

0 을 포함하는 구간들은 항상 두개 이하 선택 해야한다.

 

맨 오른쪽, 맨 왼쪽에 해당하는 구간 두개가 있으면 항상 다른 구간들은 그 구간에 포함되기 때문이다.

 

 

그리고 0 을 포함하는 구간들을 지금 선택한다고 해서 다음 구간들을 선택해 나갔을 때 최적해가 완성된다는 것이

확실치 않으므로

 

0을 포함하는 구간들을 두개 이하 포함하는 모든 경우의 수를 세 최소값을 반환하도록 함수를 구현해야한다.

 

 

 

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
 
class xyr
{
public:
double y, x, r;
std::vector<int> include;
 
xyr(double y = 0, double x = 0, double r = 0)
{
    this->y  = y;
    this->x  = x;
    this->r  = r;
}
};
 
xyr wall = xyr(0.0, 0.0, 8.0);
xyr cp[101];
 
//완전히포함되어있는거 삭제.
//y로정렬ㄹ-> 조사 .
// 중심과중심사이거리 가 반지름+ 반지름이가장 먼거 선
int mina()
{
    int ret = -1;
 
}
int main()
{
    int testCase = 0;
    int n = 0;
    double tmpy, tmpx, tmpr;
 
    std::cin>>testCase;
    for (int i = 0; i < testCase; i++)
    {
        std::cin>>n;
        for(int j = 0; j < n; j++)
        {
            std::cin>>tmpy>>tmpx>>tmpr;
            cp[j] = xyr(tmpy, tmpx, tmpr);
        }
        
    }
 
}

 

 

 

- 알고리즘 문제해결전략 397P

MINASTIRITH