[BOJ/Platinum 5] 백준 6962 Maple Roundup(C++)

문제 링크

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

6962번: Maple Roundup

 

문제

An Elmira area maple syrup producer was selected as the winner of this year's CCC (Canadian Confectionery Competition) and the judge wants to place a blue ribbon around the sugar bush. To do this, she finds the most northerly tree (if there is more than one most northerly tree, any one will do) and stands at the position of that tree, facing due East. She then turns to the right until she is facing another tree, and walks to that tree in a straight line, measuring the distance. Once again she turns right until she faces a tree, and walks to it. At each step she chooses the tree that involves turning the least angle to the right, continuing until the starting tree is reached. The total distance travelled is the length of ribbon required. Your task is to calculate this length.

입력

The input to the program will consist of a line containing an integer m followed by m data sets. Each data set consists of a line containing an integer 1 < n < 100, the number of trees in the bush, and this is followed by n lines each with an ordered pair (x, y) of integers which give the location of a tree on the Cartesian grid. You may assume that the y-axis points North while the x-axis points East.

출력

For each test case, the output from the program is the length of ribbon, to 2 decimal places, that can enclose every tree.

예제 입력 1

2
3
-1 1
1 1
1 -1
5
1 0
2 2
2 3
3 1
-1 2

예제 출력 1

6.83
10.46

알고리즘 분류

• 그레이엄스캔

풀이

기준점을 가장 북쪽에 있는 나무, 즉 Y좌표가 가장 큰 나무로 설정해준다. Y좌표가 최대인 나무가 여러 개라면 어떤 나무든 상관없으나 X좌표가 최소인 나무로 설정하였다.

그리고 그레이엄 스캔을 통해 리본을 달기 위해 필요한 나무들을 오른쪽 방향으로 이동하면서 찾아나간다.

사실 거리만 구하는 것이기 때문에 어느 방향으로 정렬하든 상관없지만 시계 방향, 즉  → ↓ ← ↑ 순으로 정렬하였다.

시계 방향임을 알 수 있는 방법은 현재 점과 그 전, 그 전 전 점이 우회전을 이룰 때이다.

세 개의 점의 CCW가 0보다 작으면 우회전을 이룬다.

정렬한 후에는 기준점부터 시작해서 모든 선분의 우회전 여부를 확인하고 우회전을 이루는 선분에 포함된 나무들을 최종적으로 고른다.

마지막으로 기준 나무부터 시작해서 현재 나무와 다음 나무 사이의 거리를 구하고 그 값들을 모두 더해주면 그것이 나무를 두르는 데 필요한 리본의 길이가 된다.

소수점 둘째 자리까지 출력해야 하는데 거리를 모두 더한 후 최종적으로 소수점 둘째 자리까지만 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct Point {
    LL X, Y;
};

int T;
LL N, X, Y, minX, maxY, First;
vector<Point> Vec;
vector<Point> CV;
double Answer;

void init() {
    minX = INF;
    maxY = -INF;
    First = 0;
    Vec.clear();
    CV.clear();
    Answer = 0;
}

LL CCW(const Point &A, const Point &B, const Point &C) {
    LL OP = A.X * B.Y + B.X * C.Y + C.X * A.Y;
    OP -= (A.Y * B.X + B.Y * C.X + C.Y * A.X);
    return OP;
}

bool Comp(const Point &A, const Point &B) {
    LL ccwValue = CCW(Vec[0], A, B);
    if (ccwValue < 0) {
        return true;
    }
    else if (ccwValue > 0) {
        return false;
    }
    if (A.Y != B.Y) {
        return (A.Y > B.Y);
    }
    return (A.X < B.X);
}

void settings() {
    for (int i = 0; i < Vec.size(); i++) {
        if ((maxY < Vec[i].Y) || ((maxY == Vec[i].Y) && (minX > Vec[i].X))) {
            minX = Vec[i].X;
            maxY = Vec[i].Y;
            First = i;
        }
    }
    Vec[First].X = Vec[0].X;
    Vec[First].Y = Vec[0].Y;
    Vec[0].X = minX;
    Vec[0].Y = maxY;
    sort(Vec.begin() + 1, Vec.end(), Comp);
    for (int i = 0; i < Vec.size(); i++) {
        while ((CV.size() >= 2) && (CCW(CV[CV.size() - 2], CV.back(), Vec[i]) >= 0)) {
            CV.pop_back();
        };
        CV.push_back(Vec[i]);
    }
}

void find_Answer() {
    for (int i = 1; i < CV.size(); i++) {
        double Sub = sqrt(abs((CV[i - 1].X - CV[i].X) * (CV[i - 1].X - CV[i].X)) + abs((CV[i - 1].Y - CV[i].Y) * (CV[i - 1].Y - CV[i].Y)));
        Answer += Sub;
    }
    double Sub = sqrt(abs((CV[0].X - CV[CV.size() - 1].X) * (CV[0].X - CV[CV.size() - 1].X)) + abs((CV[0].Y - CV[CV.size() - 1].Y) * (CV[0].Y - CV[CV.size() - 1].Y)));
    Answer += Sub;
    cout << fixed;
    cout.precision(2);
    cout << Answer << "\n";
}

void input() {
    cin >> T;
    while (T--) {
        init();
        cin >> N;
        for (int i = 0; i < N; i++) {
            cin >> X >> Y;
            Vec.push_back({X, Y});
        }
        settings();
        find_Answer();
    };
}

int main() {
    FASTIO
    input();

    return 0;
}