[Algorithm] 백준 6850 Cows - C++, Convex Hull, CCW

6850번: Cows

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct Point{
    long long x, y;
};
const auto PI = 3.1415926535;
int n, r;

vector<Point> points;

long long GetCCW(const Point& a, const Point& b, const Point& c){
    auto positive = a.x * b.y + b.x * c.y + c.x * a.y;
    auto negative = b.x * a.y + c.x * b.y + a.x * c.y;
    return positive - negative;
}

bool CompareByYPos(const Point& a, const Point& b){
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

bool CompareByCCW(const Point& a, const Point& b){
    auto ccw = GetCCW(points[0], a, b);
    return ccw ? ccw > 0 : CompareByYPos(a, b);
}


int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    points.resize(n);
    for(int i = 0; i < n; i++){
        cin >> points[i].x >> points[i].y;
    }

    
    // sort
    vector<Point> hull;

    sort(points.begin(), points.end(), CompareByYPos);
    hull.push_back(points[0]);
    sort(points.begin() + 1, points.end(), CompareByCCW);
    hull.push_back(points[1]);

    // convex hull algorithm
    for(int i = 2; i < n; i++){
        while (hull.size() >= 2){
            Point first = hull.back();
            hull.pop_back();
            Point second = hull.back();

            double ccw = GetCCW(second, first, points[i]);
            if(ccw > 0){
                hull.push_back(first);
                break;
            }
        }
        hull.push_back(points[i]);
    }

    // calculate area
    double answer = 0;
    for(int i = 1; i < hull.size() - 1; i++){
        answer += abs(GetCCW(hull[0], hull[i], hull[i+1])) * 0.5;
    }

    cout << (int)answer/50 << '\n';

}

---

 영어는 사실 구글 번역을 해도 매끄럽게 되는 수준이니 문제가 되지 않고. 이번 문제는 Convex Hull을 만든 뒤 그 볼록 껍질의 넓이를 구한 뒤 50으로 나누면 키울 수 있는 소가 나오는 문제입니다. (소 한마리당 50)

 

 여기서 넓이를 구할 때 기준점을 하나 잡고 CCW를 사용하면 수학에서 사선식을 사용해 넓이를 구하는 것과 같은 방식이 됩니다. hull 배열의 경우 이미 2번의 정렬을 거치면서 순서대로 정렬이 되었기에 정렬에 대해서는 고민할 필요가 없습니다.

삼각형 넓이 사선식 - Google 검색

 그런 다음 50으로 나눈 뒤 정수로 출력하면 됩니다!