# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
221221 | Gareth618 | Tri (CEOI09_tri) | C++14 | 785 ms | 29468 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
static int64_t ccw(const Point& a, const Point& b, const Point& c) {
return 1LL * (a.x - b.x) * (b.y - c.y) - 1LL * (b.x - c.x) * (a.y - b.y);
}
inline bool operator<(const Point& p) const {
return 1LL * y * p.x - 1LL * x * p.y < 0;
}
};
vector<Point> convexHull(vector<Point>& pts) {
vector<Point> st;
st.push_back(pts[0]);
st.push_back(pts[1]);
for (int i = 2; i < (int) pts.size(); i++) {
while (st.size() > 1 && Point::ccw(st[st.size() - 2], st[st.size() - 1], pts[i]) >= 0)
st.pop_back();
st.push_back(pts[i]);
}
return st;
}
bool below(vector<Point>& hull, Point a, Point b) {
int lo = 0, hi = hull.size() - 1;
while (hi - lo > 4) {
int m1 = (lo + hi) / 2;
int m2 = (lo + hi) / 2 + 1;
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |