백준 8927번: Squares (C++)

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

8927번: Squares

---

Solved By: Convex Hull, Rotating Calipers

 

좌표가 주어지고, w가 주어지면 사각형이 되게끔

1. a, b
2. a + w, b
3. a, b + w
4. a + w, b + w

이렇게 네 점이 사각형을 이룬다는 것을 알아야 합니다. 이 점들을 가지고서 최대 직경(Rotating Calipers)의 제곱을 구하면 됩니다.

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

struct Point{
    ll x, y;
};

Point operator-(Point a, Point b){
    Point c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}

int T;
vector<Point> v;
vector<Point> vertex;
int n;

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

ll dist(Point a, Point b){
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (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 temp = ccw(v[0], a, b);
    if(temp == 0){
        return dist(v[0], a) < dist(v[0], b);
    }
    return temp > 0;
}

void convexHull(){
    stack<Point> s;
    s.push(v[0]); s.push(v[1]);
    int next = 2;
    while(next < v.size()){
        while(s.size() >= 2){
            Point first, second;
            second = s.top(); s.pop();
            first = s.top();
            
            if(ccw(first, second, v[next]) > 0){
                s.push(second); break;
            }
        }
        s.push(v[next]);
        next++;
    }
    
    vertex.resize(s.size());
    for(int i = vertex.size() - 1; i >= 0; i--){
        vertex[i] = s.top(); s.pop();
    }
    
    return;
}

ll rotatingCalipers(){
    int pl = 0, pr = 0;
    
    for(int i = 0; i < vertex.size(); i++){
        if(vertex[i].x < vertex[pl].x) pl = i;
        if(vertex[i].x > vertex[pr].x) pr = i;
    }
    
    Point po; po.x = 0; po.y = 0;
    
    ll distValue = dist(v[pl], v[pr]);
    
    
    for(int i = 0; i < vertex.size(); i++){
        if(ccw(po, vertex[(pl + 1) % vertex.size()] - vertex[pl]
        , vertex[pr] - vertex[(pr + 1) % vertex.size()]) > 0){
            pl = (pl + 1) % vertex.size();
        }
        else{
            pr = (pr + 1) % vertex.size();
        }
        
        distValue = max(distValue, dist(vertex[pl], vertex[pr]));
    }
    
    return distValue;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    for(int t = 0; t < T; t++){
        v.clear(); vertex.clear();
        cin >> n;
        for(int i = 0; i < n; i++){
            ll a, b, w; cin >> a >> b >> w;
            v.push_back({a, b});
            v.push_back({a + w, b});
            v.push_back({a, b + w});
            v.push_back({a + w, b + w});
        }
    
        sort(v.begin(), v.end(), cmp);
        sort(v.begin() + 1, v.end(), cmp2);
    
        convexHull();
        long long result = rotatingCalipers();
        cout << result << '\n';
    }
    return 0;
}