백준 2244번: 민코프스키 합 (C++)

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

2244번: 민코프스키 합

---

Solved By: Convex Hull(Graham Scan)

 

A와 B의 점들을 {A.x + B.x, A.y + B.y}의 형태로 민코프스키 합을 구해주고, convex hull을 사용하여 만들어진 다각형의 좌표를 반시계 방향으로 출력합니다.

 

문제의 우선순위 조건에서 '2. 면적이 가장 작은 것'의 의미는 문제를 풀어도 이해하지 못했습니다.

 

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

struct Point{
    ll x, y;
};

int n, m;
vector<Point> v;

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);
}

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

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

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

void convexHull(){
    vector<int> s;
    s.push_back(0); s.push_back(1);
    int next = 2;
    
    while(next < n * m){
        while(s.size() >= 2){
            int first, second;
            second = s.back(); s.pop_back();
            first = s.back();
            
            if(ccw(v[first], v[second], v[next]) > 0){
                s.push_back(second); break;
            }
        }
        s.push_back(next++);
    }
    
    cout << s.size() << '\n';
    for(int i = 0; i < s.size(); i++){
        cout << v[s[i]].x << ' ' << v[s[i]].y << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    vector<Point> A, B;
    for(int i = 0; i < n; i++){
        ll a, b;
        cin >> a >> b;
        A.push_back({a, b});
    }
    
    for(int i = 0; i < m; i++){
        ll a, b;
        cin >> a >> b;
        B.push_back({a, b});
    }
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            v.push_back({A[i].x + B[j].x, A[i].y + B[j].y});
        }
    }
    
    sort(v.begin(), v.end(), cmp);
    sort(v.begin() + 1, v.end(), cmp2);
    
    convexHull();
    
    return 0;
}