볼록다각형(convexhull) (JUNGOL 1151)

https://jungol.co.kr/problem/1151?cursor=MTIsNiw0

---

아이디어

CCW를 이용해서 볼록 껍질을 구해주면 됩니다. 그리고 신발끈 공식을 이용해서 그 넓이를 구해주면 됩니다.

---

소스코드

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

ll CCW(pair <ll,ll> A,pair <ll,ll> B,pair <ll,ll> C)
{
    ll ax=A.first,ay=A.second,bx=B.first,by=B.second,cx=C.first,cy=C.second;
    ll ccw=ax*(by-cy)+bx*(cy-ay)+cx*(ay-by);
    if (ccw<0) return -1;
    if (ccw==0) return 0;
    if (ccw>0) return 1;
}
bool ycmp(pair <ll,ll> A,pair <ll,ll> B)
{
    if (A.second!=B.second) return A.second<B.second;
    return A.first<B.first;
}
pair <ll,ll> lowdot;
bool cmp(pair <ll,ll> A,pair <ll,ll> B)
{
    return CCW(lowdot,A,B)>0;
}

vector <pair <ll,ll> > ConvexHull(vector <pair <ll,ll> > v)
{
    ll N=v.size();
    sort (v.begin(),v.end(),ycmp); lowdot=v[0];
    sort (v.begin()+1,v.end(),cmp);

    ll stk[55]={0,1},top=2;
    for (ll i=2;i<N;i++)
    {
        while (top>=2 && CCW(v[stk[top-2]],v[stk[top-1]],v[i])<=0) top--;
        stk[top++]=i;
    }

    vector <pair <ll,ll> > res;
    for (ll i=0;i<top;i++)
        res.push_back(v[stk[i]]);
    return res;
}
ll Area(vector <pair <ll,ll> > v)
{
    ll N=v.size();
    v.push_back(v[0]);

    ll res=0;
    for (ll i=0;i<N;i++)
        res+=v[i].first*v[i+1].second-v[i].second*v[i+1].first;
    return abs(res);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,x,y;
    vector <pair <ll,ll> > v;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>x>>y;
        v.push_back({x,y});
    }

    ll res=Area(ConvexHull(v));

    if (res%2==1) cout<<res/2<<".5";
    else cout<<res/2;
}