[c++] 백준 #11447 Colby’s Costly Collectibles (190903)

< 풀이 >

x(1,0) y(1,1) z(-1,1)로 하고 신발끈 공식을 쓰면 된다. 신발끈 공식은 다각형의 넓이를 구하는 방법으로 다각형이 볼록이든 오목이든 가능하다.

** 문제를 풀 때 double을 쓰면 오차가 생기기 때문에 최대한 안쓰는 것이 좋다.

 

< 소스 코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int abs(int a){
    if (a>=0) return a;
    else return -a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;
    while(T--){
        int N; cin >> N;
        vector<ii> points;
        int x = 0;
        int y = 0;
        for(int i=0; i<N;i++){  
            char a; int b;
            cin >> a >> b;
            if (a=='x'){ // (1, 0)
                x += 2*b;
            }
            else if (a=='y'){ // (1, 1)
                x += b;
                y += b;    
            }
            else { // (-1, 1)
                x -= b;
                y += b;
            }
            points.pb({x, y});
        }
        int ans = 0;
        for(int i=0; i<N;i++){
            int j = (i + 1) % N;
            ans += points[i].first*points[j].second;
            ans -= points[i].second*points[j].first;
        }
        cout << abs(ans)/2 << '\n'; 
    }
    return 0;
}