| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1308508 | vili | SIR (COI15_sir) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
ll cross(const pii& a, const pii& b, const pii& c) {
// (b - a) x (c - a)
return (b.first - a.first) * (c.second - a.second)
- (b.second - a.second) * (c.first - a.first);
}
ll area2(const pii& a, const pii& b, const pii& c) {
return llabs(cross(a,b,c));
}
/* Monotone chain convex hull */
vector<pii> convex_hull(vector<pii> pts) {
if (pts.size() <= 1) return pts;
sort(pts.begin(), pts.end());
vector<pii> hull;
// lower hull
for (auto &p : pts) {
while (hull.size() >= 2 &&
cross(hull[hull.size()-2], hull.back(), p) <= 0)
hull.pop_back();
hull.push_back(p);
}
// upper hull
size_t lower_size = hull.size();
for (int i = (int)pts.size() - 2; i >= 0; i--) {
w
