백준 6850번: Cows (C++)

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

6850번: Cows

---

Solved By: Convex Hull

 

넓이의 최댓값을 구하기 위해 Convex Hull을 이용하여 제일 넓은 볼록 껍질을 구하였습니다.

 

다각형의 넓이는 두 벡터의 CCW를 구하면 두 벡터가 이루는 평행사변형의 넓이가 나온다는 것을 알고 있어야 합니다.

이 과정에서 절대 중간에서 절댓값으로 취하여 더해주면 안 됩니다. ccw의 값이 음수나 양수가 나오든 다 더한 절댓값이 다각형의 넓이라는 것을 알고 있어야 합니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#define ll long long
using namespace std;

typedef struct{
    ll x, y;
} Point;

int n;
vector<Point> v;

ll dist(Point a, Point b){
    return powl(a.x - b.x, 2) + powl(a.y - b.y, 2);
}

ll ccw(Point a, Point b, Point c){
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(Point a, Point b){
    if(a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

bool cmp2(Point a, Point b){
    ll ccwv = ccw(v[0], a, b);
    if(ccwv == 0){
        return dist(v[0], a) < dist(v[0], b);
    }
    return ccwv > 0;
}

ll convexHull(){
    stack<int> s;
    s.push(0); s.push(1);
    int next = 2;
    while(next < n){
        while(s.size() >= 2){
            int first, second;
            second = s.top(); s.pop();
            first = s.top();
            
            if(ccw(v[first], v[second], v[next]) > 0){
                s.push(second); break;
            }
        }
        s.push(next++);
    }
    
    // 면적 넓이
    // ccw는 두 벡터가 이루는 평행사변형의 넓이와 같다.
    
    Point p = v[s.top()];
    s.pop();
    ll result = 0;
    while(s.size() >= 2){
        int first = s.top(); s.pop();
        int second = s.top();
        
        result += ccw(p, v[first], v[second]) / 2;
    }
    
    
    return result;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        ll a, b; cin >> a >> b;
        v.push_back({a, b});
    }
    
    sort(v.begin(), v.end(), cmp);
    sort(v.begin() + 1, v.end(), cmp2);
    
    ll result = abs(convexHull());
    cout << result / 50;
    return 0;
}