백준 2477번: 참외밭 (C++)

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

2477번: 참외밭

---

Level: Silver III

Solved By: CCW, Geometry

 

문제에서 말했다시피 육각형은 어떻게 그려도 ㄱ-자 육각형입니다.

그래서 문제를 아래 그림과 같이 재정의 해볼 수 있었습니다.

전체적인 면적에서 부분 면적을 빼주는 방식입니다.

그럼 알아낼 것은 Sub Area를 구분 짓는 꺾인 점이 어딘지 알면 됩니다.

꺾인 점을 기준으로 앞 뒤 점을 가져오면 Sub Area의 넓이를 구할 수 있기 때문입니다.

 

이러한 꺾인 점을 구하는 방식은 CCW를 이용했습니다.

시계방향에 위치한다면 CCW가 음수 값이 나오기 때문에 이러한 점을 이용했습니다.

#include <iostream>
#include <vector>
using namespace std;

int K;

struct Point{
    int x, y;
};

vector<Point> points;

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

int get_area(Point a, Point b){
    return abs(a.x - b.x) * abs(a.y - b.y);
}

int main(){
    cin >> K;
    
    int temp_x = 0, temp_y = 0;
    points.push_back({temp_x, temp_y}); // start point
    
    for(int i = 0; i < 5; i++){
        int dir, dist; cin >> dir >> dist;
        
        if(dir == 1) temp_x += dist; // E
        else if(dir == 2) temp_x -= dist; // W
        else if(dir == 3) temp_y -= dist; // S
        else temp_y += dist; // N
        
        points.push_back({temp_x, temp_y});
    }
    int a, b; cin >> a >> b; // trash
    
    int total_area = 0;
    int max_x = -10000, min_x = 10000;
    int max_y = -10000, min_y = 10000;
    for(int i = 0; i < 6; i++){
        max_x = max(max_x, points[i].x);
        min_x = min(min_x, points[i].x);
        max_y = max(max_y, points[i].y);
        min_y = min(min_y, points[i].y);
    }
    
    total_area = get_area({min_x, min_y}, {max_x, max_y});
    
    int sub_area = 0;
    for(int i = 0; i < 6; i++){ // 꺾인 점 찾기
        int index = i + 6; // overflow 방지
        
        Point before = points[(index - 1) % 6];
        Point now = points[index % 6];
        Point after = points[(index + 1) % 6];
        
        int ccw_res = ccw(before, now, after);
        if(ccw_res < 0){ // 꺾인 점이라면?
            sub_area = get_area(before, after);
        }
    }
    
    cout << K * (total_area - sub_area);
    return 0;
}