백준 25051 천체 관측

 

https://www.acmicpc.net/problem/25051

25051번: 천체 관측

 

풀이 

0. 문제를풀기 앞서서 공부해야할것

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

간단한 투포인터 문제를 풀어보시는걸 추천드립니다.

 

각도 θ를 구하는 공식

 

해당 문제에서는 점의 좌표를 통해서 각도를 구해야합니다.

위의 공식을 이용해서 각도를 구할 수 있습니다.

 

필자는 다음과 같은 방식으로 각도를 구하는 코드를 작성했습니다. 

        float angle = (float)(180.0 / (atan(1) * 4) * atan2(y, x));
        angle = fmod(angle + 360.0, 360.0);

 

1. 핵심 아이디어

 

예제1번을 예시로 설명드리겠습니다.

먼저 별들의 위치는 다음과 같습니다.

 

별위치(빨강색)와 별의 가치(주황색)가 적혀있다.

 

당연하게도 망원경시야 90도 안의 별들만 보면됩니다.

원점을 중심으로 별들이 어느정도의 각도에 위치하는지 전처리를 먼저해줍니다.

(위의 공식을 사용합니다.)

 

 

그후 각도를 중심으로 별들을 정렬합니다.

 

(각도, 별의 가치)

 

투포인터를 사용하기위한 변수 l,r를 선언해줍니다.

l과 r은 관측하고 있는 별들중 가장 가장자리의 별의 인덱스 값입니다.

l과 r이 가리키는 별의 사이의 각도가 90도가 유지되도록하면서 탐색해야합니다.

 

각도가 90도 이하라면 r를 증가시켜서 별들을 포함시키고

90도보다 크다면 l를 감소시켜서 별들을 제거해줍니다.

 

아래는 이해를 돕기위한 투포인터의 실행과정입니다.

 

l  = 0, r = 0인 상태 사이의 각도는 0도입니다.

90도 이하입니다.

3점을 포함시키고 r을 증가시킵니다.

 

 

l  = 0, r = 1인 상태 사이의 각도는 45도입니다.

90도 이하입니다.

8점을 포함시키고 r을 증가시킵니다.

 

l  = 0, r = 2인 상태 사이의 각도는 90도입니다.

90도 이하입니다.

6점을 포함시키고 r을 증가시킵니다.

 

 

 

l  = 0, r = 3인 상태 사이의 각도는 135도입니다.

90도를 넘겼습니다.

l를 증가시키고 3점을 빼줍니다.

 

 

 

l  = 1, r = 3인 상태 사이의 각도는 90도입니다.

90도 이하입니다.

5점을 포함시키고 r을 증가시킵니다.

 

 

투포인터는 다음과 같고 망원경 P의 값에 따라서 관측이 가능한지 아닌지 예외처리하시면됩니다.

 

 

하지만 이 문제는 원으로 탐색해야하는 경우이므로 조심해야할점이 생깁니다!!

 

 

 

원이기 때문에 다음과 같이 한바퀴 돌아서 r이 왼쪽에 l이 오른쪽에 놓이는 일도 고려해야합니다.

다행이 생각보다 간단히 고려할 수 있습니다.

 

 

뒤에 똑같은 별들을 추가해서 원인 경우를 고려할 수 있습니다.

 

 

마지막으로 아무것도 관측 못했을 경우도 고려해야합니다.(문제의 예제4의 케이스)

 

answer = max(answer, 0-P);

으로 해당 경우를 처리해줍니다.

 

 

 

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

#define Debug(a,b) cout << a << " " << b << endl
#define Init(a,b) memset(a,b,sizeof(a))

const float INF = 1e18;
const int Dic[8][2] = { {0,1},{0,-1},{1,0},{-1,0} ,{1,1},{-1,-1},{1,-1},{-1,1} };

//////////////////////////////////////////////////////////////////////// 

int N, M;
vector<tuple<float, int, int>> Star;
int ans = -INF;
float GetAngleDis(int l, int r)
{
    //l과 r사이의 각도
    float v = get<0>(Star[r]) - get<0>(Star[l]);
    if (v < 0)
        v = fmod(v + 360.0, 360.0);
    return v;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    std::cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int x, y, s;
        std::cin >> x >> y >> s;

        //각 별들의 각도를 전처리
        float angle = (float)(180.0 / (atan(1) * 4) * atan2(y, x));
        angle = fmod(angle + 360.0, 360.0);
        Star.emplace_back(angle, x * x + y * y, s);
    }

    //별들을 각도순으로 정렬
    sort(Star.begin(), Star.end());

    //뒤에 똑같은 별들을 연결시켜준다.
    for (int i = 0; i < N; i++)
    {
        float angle = get<0>(Star[i]);
        int dis = get<1>(Star[i]);
        int s = get<2>(Star[i]);
        Star.emplace_back(angle, dis, s);
    }

    for (int i = 0; i < M; i++)
    {
        int a;
        std::cin >> a;
        int l = 0;
        int ret = 0;
        for (int r = 0; r < N*2; r++)
        {
            while (GetAngleDis(l, r) > 90)
            {
                //각도가 90도를 넘겼다.
                //l를 증가시킨다.
                float lDis = get<1>(Star[l]);
                float lValue = get<2>(Star[l]);
                if (a >= lDis)
                {
                    //이전에 포함했던 별이다.
                    //점수를 제거해준다.
                    ret -= lValue;
                    ans = max(ans, ret - a);
                }
                l++;
            }

            //여기까지왔으면 각도는 90도 안쪽이다.
            float rDis = get<1>(Star[r]);
            float rValue = get<2>(Star[r]);
            if (a >= rDis)
            {
                //포함시킬수 있는 별이다.
                //별들의 점수를 포함시켜준다.
                ret += rValue;
                ans = max(ans, ret - a);
            }
        }

        ans = max(ans, 0 - a); //아무것도 관측을 못했을 경우를 처리
    }

    std::cout << ans << endl;

}