BOJ 10254 고속도로

1 개요

BOJ 10254 고속도로

• 백준 온라인 저지 10254번 문제
• BOJ 48단계

2 C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Point;
int T, n;
vector<Point> cities;

int ccw(Point a, Point b, Point c) {
    ll res = a.first * b.second + b.first * c.second + c.first * a.second;
    res -= b.first * a.second + c.first * b.second + a.first * c.second;
    if (res > 0) return 1;
    if (res) return -1;
    return 0;
}

ll dist(Point a, Point b) {
    ll dx = a.first - b.first;
    ll dy = a.second - b.second;
    return dx * dx + dy * dy;
}

bool check(Point s, Point e, Point ss, Point ee) {
    Point t = {e.first - s.first, e.second - s.second};
    Point tt = {ee.first - ss.first, ee.second - ss.second};
    return ccw({0, 0}, t, tt) >= 0;
}

void solve() {
    vector<Point> hull;
    swap(cities[0], *min_element(cities.begin(), cities.end()));
    sort(cities.begin() + 1, cities.end(), [&](Point &a, Point &b) {
        int cw = ccw(cities[0], a, b);
        if (cw) return cw > 0;
        return dist(cities[0], a) < dist(cities[0], b);
    });
    for (auto &i : cities) {
        while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), i) <= 0)
            hull.pop_back();
        hull.push_back(i);
    }
    Point answer[2];
    ll maxDist = 0;
    int pt = 0;
    for (int i = 0; i < hull.size(); i++) {
        ll currDist;
        while (pt + 1 < hull.size() && check(hull[i], hull[i + 1], hull[pt], hull[pt + 1])) {
            currDist = dist(hull[i], hull[pt]);
            if (currDist > maxDist) {
                maxDist = currDist;
                answer[0] = hull[i];
                answer[1] = hull[pt];
            }
            pt++;
        }
        currDist = dist(hull[i], hull[pt]);
        if (currDist > maxDist) {
            maxDist = currDist;
            answer[0] = hull[i];
            answer[1] = hull[pt];
        }
    }
    cout << answer[0].first << ' ' << answer[0].second << ' ';
    cout << answer[1].first << ' ' << answer[1].second << '\n';
}

void sub() {
    cin >> n;
    cities.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> cities[i].first >> cities[i].second;
    }
    solve();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        sub();
    }
}