QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#278470 | #7906. Almost Convex | jiufeng | WA | 344ms | 4192kb | C++17 | 11.2kb | 2023-12-07 16:33:07 | 2023-12-07 16:33:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
using T = i64;
const T Eps = 0;
int sign(T a) {
return a < -Eps ? -1 : a > Eps;
}
int cmp(T a, T b) {
return sign(a - b);
}
struct Point {
T x;
T y;
Point(T x_ = T(0), T y_ = T(0)) : x(x_), y(y_) {}
Point &operator+=(Point p) & {
x += p.x;
y += p.y;
return *this;
}
Point &operator-=(Point p) & {
x -= p.x;
y -= p.y;
return *this;
}
Point &operator*=(T v) & {
x *= v;
y *= v;
return *this;
}
Point &operator*=(Point p) & {
tie(x, y) = pair<T, T>{x * p.x - y * p.y, x * p.y + y * p.x};
return *this;
}
Point &operator/=(Point p) & {
auto t = p.x * p.x + p.y * p.y;
tie(x, y) = pair<T, T>{(x * p.x + y * p.y) / t, (y * p.x - x * p.y) / t};
return *this;
}
bool operator<(Point p) const {
int c = cmp(y, p.y);
if (c) return c == -1;
return cmp(x, p.x) == -1;
}
Point operator-() const {
return Point(-x, -y);
}
friend Point operator+(Point a, Point b) {
return a += b;
}
friend Point operator-(Point a, Point b) {
return a -= b;
}
friend Point operator*(Point a, T b) {
return a *= b;
}
friend Point operator*(T a, Point b) {
return b *= a;
}
friend Point operator*(Point a, Point b) {
return a *= b;
}
friend Point operator/(Point a, Point b) {
return a /= b;
}
friend bool operator==(Point a, Point b) {
return a.x == b.x && a.y == b.y;
}
friend bool operator!=(Point a, Point b) {
return !(a == b);
}
double at() {
return atan2(1.0 * y, 1.0 * x);
}
};
T dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
// area of triangle with Point(0, 0)
T cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
T square(Point p) {
return dot(p, p);
}
double length(Point p) {
return sqrt(double(square(p)));
}
struct Line {
Point a;
Point b;
Line(Point a_ = Point(), Point b_ = Point()) : a(a_), b(b_) {}
};
Point rotate(Point a) {
return Point(-a.y, a.x);
}
int sgn(Point a) {
return a.y > 0 || (a.y == 0 && a.x > 0) ? 1 : -1;
}
bool pointOnLineLeft(Point p, Line l) {
return cross(l.b - l.a, p - l.a) > 0;
}
Point lineIntersection(Line l1, Line l2) {
return l1.a + (l1.b - l1.a) * (cross(l2.b - l2.a, l1.a - l2.a) / cross(l2.b - l2.a, l1.a - l1.b));
}
bool pointOnSegment(Point p, Line l) {
return cross(p - l.a, l.b - l.a) == T(0) && min(l.a.x, l.b.x) <= p.x && p.x <= max(l.a.x, l.b.x)
&& min(l.a.y, l.b.y) <= p.y && p.y <= max(l.a.y, l.b.y);
}
bool pointInPolygon(Point a, vector<Point> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
if (pointOnSegment(a, Line(p[i], p[(i + 1) % n]))) {
return true;
}
}
int t = 0;
for (int i = 0; i < n; i++) {
auto u = p[i];
auto v = p[(i + 1) % n];
if (u.x < a.x && v.x >= a.x && pointOnLineLeft(a, Line(v, u))) {
t ^= 1;
}
if (u.x >= a.x && v.x < a.x && pointOnLineLeft(a, Line(u, v))) {
t ^= 1;
}
}
return t == 1;
}
// 0 : not intersect
// 1 : strictly intersect
// 2 : overlap
// 3 : intersect at endpoint
tuple<int, Point, Point> segmentIntersection(Line l1, Line l2) {
if (max(l1.a.x, l1.b.x) < min(l2.a.x, l2.b.x)) {
return {0, Point(), Point()};
}
if (min(l1.a.x, l1.b.x) > max(l2.a.x, l2.b.x)) {
return {0, Point(), Point()};
}
if (max(l1.a.y, l1.b.y) < min(l2.a.y, l2.b.y)) {
return {0, Point(), Point()};
}
if (min(l1.a.y, l1.b.y) > max(l2.a.y, l2.b.y)) {
return {0, Point(), Point()};
}
if (cross(l1.b - l1.a, l2.b - l2.a) == T(0)) {
if (cross(l1.b - l1.a, l2.a - l1.a) != T(0)) {
return {0, Point(), Point()};
} else {
auto maxx1 = max(l1.a.x, l1.b.x);
auto minx1 = min(l1.a.x, l1.b.x);
auto maxy1 = max(l1.a.y, l1.b.y);
auto miny1 = min(l1.a.y, l1.b.y);
auto maxx2 = max(l2.a.x, l2.b.x);
auto minx2 = min(l2.a.x, l2.b.x);
auto maxy2 = max(l2.a.y, l2.b.y);
auto miny2 = min(l2.a.y, l2.b.y);
Point p1(max(minx1, minx2), max(miny1, miny2));
Point p2(min(maxx1, maxx2), min(maxy1, maxy2));
if (!pointOnSegment(p1, l1)) {
swap(p1.y, p2.y);
}
if (p1 == p2) {
return {3, p1, p2};
} else {
return {2, p1, p2};
}
}
}
auto cp1 = cross(l2.a - l1.a, l2.b - l1.a);
auto cp2 = cross(l2.a - l1.b, l2.b - l1.b);
auto cp3 = cross(l1.a - l2.a, l1.b - l2.a);
auto cp4 = cross(l1.a - l2.b, l1.b - l2.b);
if ((cp1 > T(0) && cp2 > T(0)) || (cp1 < T(0) && cp2 < T(0)) || (cp3 > T(0) && cp4 > T(0)) || (cp3 < T(0) && cp4 < T(0))) {
return {0, Point(), Point()};
}
Point p = lineIntersection(l1, l2);
if (cp1 != T(0) && cp2 != T(0) && cp3 != T(0) && cp4 != T(0)) {
return {1, p, p};
} else {
return {3, p, p};
}
}
bool segmentInPolygon(Line l, vector<Point> p) {
int n = p.size();
if (!pointInPolygon(l.a, p)) {
return false;
}
if (!pointInPolygon(l.b, p)) {
return false;
}
for (int i = 0; i < n; i++) {
auto u = p[i];
auto v = p[(i + 1) % n];
auto w = p[(i + 2) % n];
auto [t, p1, p2] = segmentIntersection(l, Line(u, v));
if (t == 1) {
return false;
}
if (t == 0) {
continue;
}
if (t == 2) {
if (pointOnSegment(v, l) && v != l.a && v != l.b) {
if (cross(v - u, w - v) > 0) {
return false;
}
}
} else {
if (p1 != u && p1 != v) {
if (pointOnLineLeft(l.a, Line(v, u))
|| pointOnLineLeft(l.b, Line(v, u))) {
return false;
}
} else if (p1 == v) {
if (l.a == v) {
if (pointOnLineLeft(u, l)) {
if (pointOnLineLeft(w, l)
&& pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, l)
|| pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
} else if (l.b == v) {
if (pointOnLineLeft(u, Line(l.b, l.a))) {
if (pointOnLineLeft(w, Line(l.b, l.a))
&& pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, Line(l.b, l.a))
|| pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
} else {
if (pointOnLineLeft(u, l)) {
if (pointOnLineLeft(w, Line(l.b, l.a))
|| pointOnLineLeft(w, Line(u, v))) {
return false;
}
} else {
if (pointOnLineLeft(w, l)
|| pointOnLineLeft(w, Line(u, v))) {
return false;
}
}
}
}
}
}
return true;
}
vector<Point> hp(vector<Line> lines) {
sort(lines.begin(), lines.end(), [&](auto l1, auto l2) {
auto d1 = l1.b - l1.a;
auto d2 = l2.b - l2.a;
if (sgn(d1) != sgn(d2)) {
return sgn(d1) == 1;
}
return cross(d1, d2) > 0;
});
deque<Line> ls;
deque<Point> ps;
for (auto l : lines) {
if (ls.empty()) {
ls.push_back(l);
continue;
}
while (!ps.empty() && !pointOnLineLeft(ps.back(), l)) {
ps.pop_back();
ls.pop_back();
}
while (!ps.empty() && !pointOnLineLeft(ps[0], l)) {
ps.pop_front();
ls.pop_front();
}
if (cross(l.b - l.a, ls.back().b - ls.back().a) == 0) {
if (dot(l.b - l.a, ls.back().b - ls.back().a) > 0) {
if (!pointOnLineLeft(ls.back().a, l)) {
assert(ls.size() == 1);
ls[0] = l;
}
continue;
}
return {};
}
ps.push_back(lineIntersection(ls.back(), l));
ls.push_back(l);
}
while (!ps.empty() && !pointOnLineLeft(ps.back(), ls[0])) {
ps.pop_back();
ls.pop_back();
}
if (ls.size() <= 2) {
return {};
}
ps.push_back(lineIntersection(ls[0], ls.back()));
return vector<Point>(ps.begin(), ps.end());
}
T crossA(Point a, Point b, Point c) {
return cross(b - a, c - a);
}
T crossOp(Point a, Point b, Point c) {
return sign(crossA(a, b, c));
}
vector<Point> converHull(vector<Point> p) {
int n = p.size();
if (n < 2) return p;
// sort(p.begin(), p.end(), [&](Point a, Point b) {
// if (a.x == b.x) {
// return a.x < b.x;
// } else {
// return a.y < b.y;
// }
// });
sort(p.begin(), p.end());
vector<Point> q(2 * n);
int k = 0;
for (int i = 0; i < n; q[k++] = p[i++]) {
while (k > 1 && crossOp(q[k - 2], q[k - 1], p[i]) <= 0) {
k--;
}
}
for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--]) {
while (k > t && crossOp(q[k - 2], q[k - 1], p[i]) <= 0) {
k--;
}
}
q.resize(k - 1);
return q;
}
// need to unique the first
vector<Point> converHullNonStrict(vector<Point> p) {
int n = p.size();
if (n < 2) return p;
sort(p.begin(), p.end(), [&](Point a, Point b) {
if (a.x == b.x) {
return a.x < b.x;
} else {
return a.y < b.y;
}
});
vector<Point> q(2 * n);
int k = 0;
for (int i = 0; i < n; q[k++] = p[i++]) {
while (k > 1 && crossOp(q[k - 2], q[k - 1], p[i]) < 0) {
k--;
}
}
for (int i = n - 2, t = k; i >= 0; q[k++] = p[i--]) {
while (k > t && crossOp(q[k - 2], q[k - 1], p[i]) < 0) {
k--;
}
}
q.resize(k - 1);
return q;
}
T area(vector<Point> p) {
int n = (int) p.size();
sort(p.begin(), p.end(), [&](Point a, Point b) {
return atan2(a.y, a.x) < atan2(b.y, b.x);
});
T ans = 0;
for (int i = 0; i < n; i++) {
ans += cross(p[i], p[(i + 1) % n]);
}
return ans / 2;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<Point> p(n);
for (int i = 0; i < n; i++) {
T x, y;
cin >> x >> y;
p[i] = Point(x, y);
}
auto q = converHull(p);
set<Point> s(q.begin(), q.end());
vector<bool> inhull(n);
for (int i = 0; i < n; i++) {
if (s.count(p[i])) {
inhull[i] = true;
}
}
if ((int) q.size() == n) {
cout << "1\n";
return 0;
}
function<int(int)> calc = [&](int s) {
vector<pair<Point, int>> v;
vector<double> at(n);
for (int i = 0; i < n; i++) {
if (i == s) continue;
v.emplace_back(p[i] - p[s], i);
at[i] = v.back().first.at();
}
sort(v.begin(), v.end(), [&](auto a, auto b) {
return at[a.second] < at[b.second];
});
int fi = 0, ls = n - 2;
while (inhull[v[fi].second]) {
fi++;
}
while (inhull[v[ls].second]) {
ls--;
}
int cnt = fi + n - 2 - ls - 1;
for (int i = fi, j = fi; i <= ls; i = j) {
j = i + 1;
while (j <= ls && inhull[v[i].second] && inhull[v[j].second]) {
j++;
}
if (inhull[v[i].second]) {
cnt += j - i - 1;
}
}
return cnt;
};
i64 ans = 1;
for (int i = 0; i < n; i++) {
if (inhull[i]) continue;
ans += calc(i);
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4192kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4064kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 344ms
memory: 4180kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
-967
result:
wrong answer 1st numbers differ - expected: '718', found: '-967'