QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#527887 | #7906. Almost Convex | dechancer | TL | 4ms | 19032kb | C++20 | 11.3kb | 2024-08-22 21:43:13 | 2024-08-22 21:43:14 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = double;
constexpr ld eps = 1e-9;
const ld pi = acos(-1.l);
template <class T>
struct Point {
T x, y;
Point(T x = 0, T y = 0) : x(x), y(y) {}
template <class U>
operator Point<U>() {
return Point<U>(U(x), U(y));
}
Point& operator+=(Point b) { return x += b.x, y += b.y, *this; }
Point& operator-=(Point b) { return x -= b.x, y -= b.y, *this; }
Point& operator*=(T t) { return x *= t, y *= t, *this; }
Point& operator/=(T t) { return x /= t, y /= t, *this; }
Point operator-() { 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 t) { return a *= t; }
friend Point operator*(T t, Point b) { return b *= t; }
friend Point operator/(Point a, T t) { return a /= t; }
friend Point operator/(T t, Point b) { return b /= t; }
friend bool operator==(Point a, Point b) { return a.x == b.x and a.y == b.y; }
friend istream& operator>>(istream& is, Point& a) { return is >> a.x >> a.y; }
friend ostream& operator<<(ostream& os, Point& a) {
return os << '(' << a.x << ',' << a.y << ')';
}
friend bool operator<(const Point& a, const Point& b) {
return a.x != b.x ? a.x < b.x : a.y < b.y;
}
int sign() { return y > 0 or (y == 0 and x > 0) ? 1 : -1; }
T square() { return x * x + y * y; }
T len() { return sqrt(square()); }
Point rotate(T r) {
return Point(x * cos(r) - y * sin(r), x * sin(r) + y * cos(r));
}
friend T dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
friend T dot(Point a, Point b, Point c) { return dot(b - a, c - a); }
friend T cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
friend T cross(Point a, Point b, Point c) { return cross(b - a, c - a); }
friend T dist(Point a, Point b) { return (a - b).len(); }
friend T angle(Point a, Point b) {
return acos(dot(a, b) / a.len() / b.len());
}
friend bool isParallel(Point a, Point b) { return cross(a, b) == 0; }
friend bool isPerpendicular(Point a, Point b) { return dot(a, b) == 0; }
// return the square of dist between the closest points in the plane
friend T colsestPoint(vector<Point>& a) {
vector<Point> b(a.size());
sort(a.begin(), a.end());
auto divide = [&](auto&& self, auto l, auto r) -> T {
if (l + 1 == r)
return LLONG_MAX;
auto mid = l + (r - l) / 2;
T midx = mid->x;
T d = min(self(self, l, mid), self(self, mid, r));
inplace_merge(l, mid, r, [&](auto& a, auto& b) { return a.y < b.y; });
b.clear();
auto square = [](T x) { return x * x; };
for (auto i = l; i < r; i++) {
if (square(i->x - midx) < d)
b.push_back(*i);
}
for (int i = 0; i < b.size(); i++) {
for (int j = i + 1; j < b.size() and square(b[j].y - b[i].y) < d; j++) {
d = min(d, (b[j] - b[i]).square());
}
}
return d;
};
return divide(divide, a.begin(), a.end());
}
};
template <class T>
struct Line {
Point<T> a, b;
Line(Point<T> a = {}, Point<T> b = {}) : a(a), b(b) {}
friend bool operator<(const Line& u, const Line& v) {
return u.a != v.a ? u.a < v.a : u.b < v.b;
}
Line rotate(T r, Point<T> pivot) {
return Line(pivot, pivot + (b - a).rotate(r));
}
Line getVerticalLine(Point<T> p) { return rotate(pi / 2, p); }
Line getParallelLine(Point<T> p) { return rotate(0, p); }
friend bool isParallel(Line u, Line v) {
return isParallel(u.b - u.a, v.b - v.a);
}
friend bool isPerpendicular(Line u, Line v) {
return isPerpendicular(u.b - u.a, v.b - v.a);
}
friend bool isCollinear(Line u, Line v) {
return cross(u.a, u.b, v.a) == 0 and cross(u.a, u.b, v.b) == 0;
}
bool pointOnLine(Point<T> p) { return cross(a, b, p) == 0; }
bool pointOnLineLeft(Point<T> p) { return cross(a, b, p) > 0; }
bool pointOnLineRight(Point<T> p) { return cross(a, b, p) < 0; }
bool pointOnSegment(Point<T> p) {
return pointOnLine(p) and min(a.x, b.x) <= p.x and p.x <= max(a.x, b.x) and
min(a.y, b.y) <= p.y and p.y <= max(a.y, b.y);
}
friend bool lineIntersectLine(Line u, Line v) { return !isParallel(u, v); }
friend bool lineIntersectSegment(Line u, Line v) {
if (isParallel(u, v)) {
return u.pointOnSegment(v.a) or u.pointOnSegment(v.b);
}
return cross(u.b - u.a, v.a - u.a) * cross(u.b - u.a, v.b - u.b) <= 0;
}
friend bool segmentIntersectSegment(Line u, Line v) {
return lineIntersectSegment(u, v) and lineIntersectSegment(v, u);
}
T pointToLine(Point<T> p) { return abs(cross(a, b, p)) / (b - a).len(); }
T pointToSegment(Point<T> p) {
T res = min(dist(a, p), dist(b, p));
Line l = getVerticalLine(p);
if (lineIntersectSegment(l, *this)) {
res = min(res, pointToLine(p));
}
return res;
}
friend T segmentToSegment(Line u, Line v) {
if (segmentIntersectSegment(u, v))
return 0;
return min({u.pointToSegment(v.a), u.pointToSegment(v.b),
v.pointToSegment(u.a), v.pointToSegment(u.b)});
}
friend Point<T> intersection(Line u, Line v) {
return u.a + (u.b - u.a) * (cross(v.b - v.a, u.a - v.a) /
cross(v.b - v.a, u.a - u.b));
}
};
template <class T>
struct Polygon {
int n;
vector<Point<T>> p;
Polygon() {}
Polygon(int n) { init(n); }
void init(int n) {
this->n = n;
p.assign(n, {});
}
void norm() {
int i = 0;
for (int j = 0; j < n; j++) {
if (p[j].y < p[i].y or (p[j].y == p[i].y and p[j].x < p[i].x))
i = j;
}
rotate(p.begin(), p.begin() + i, p.end());
}
void polarSort(Point<T> pivot = {}) {
auto angle = [](auto& a) { return atan2(a.y, a.x); };
sort(p.begin(), p.end(), [&](auto a, auto b) {
a -= pivot, b -= pivot;
return angle(a) < angle(b);
});
}
bool pointInPolygon(Point<T> a) {
if (cross(p[0], p[1], a) < 0 or cross(p[0], p[n - 1], a) > 0)
return false;
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (cross(p[0], p[mid], a) > 0)
l = mid;
else
r = mid - 1;
}
Line line(p[l], p[l + 1]);
return line.pointOnLineLeft(a) or line.pointOnSegment(a);
}
friend bool polygonIntersectPolygon(Polygon& a, Polygon& b) {
return any_of(a.p.begin(), a.p.end(),
[&](auto& x) { return b.pointInPolygon(x); }) or
any_of(b.p.begin(), b.p.end(),
[&](auto& x) { return a.pointInPolygon(x); });
}
T getPerimeter() {
T res{};
for (int i = 0; i < n; i++) {
res += dist(p[i], p[(i + 1) % n]);
}
return res;
}
// area shouldn't be taken as abs-val when calcs the center
// area should be taken as abs-bal when calcs the area
T getArea() {
T res{};
for (int i = 0; i < n; i++) {
res += cross(p[i], p[(i + 1) % n]);
}
return res / 2;
}
Point<T> getCenter() {
Point<T> res;
T area = getArea();
if (area == 0)
return res;
for (int i = 0; i < n; i++) {
res += (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
}
return res / 6 / area;
}
auto& getHull(const T eps = 0) {
vector<Point<T>> h, stk;
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
h.clear();
auto stkR = [&](int i) { return stk.rbegin()[i]; };
auto handle = [&]() {
stk.clear();
for (auto& a : p) {
while (stk.size() >= 2 and cross(stkR(1), stkR(0), a) <= eps) {
stk.pop_back();
}
stk.push_back(a);
}
h.insert(h.end(), stk.begin(), stk.end() - 1);
};
handle();
reverse(p.begin(), p.end());
handle();
swap(p, h);
n = p.size();
return p;
}
// shouldn't run getHull at the beginning
bool isConvex() {
int prev = n;
getHull(-eps);
return prev == n;
}
// run getHull first
auto getAntiPodal() {
vector ap(n, 0);
for (int i = 0, j = 1; i < n; i++) {
auto &a = p[i], &b = p[(i + 1) % n];
while (cross(a, b, p[j]) < cross(a, b, p[(j + 1) % n])) {
j = (j + 1) % n;
}
ap[i] = j;
}
return ap;
}
// return the square of diameter
T getDiameter() {
T res{};
auto ap = getAntiPodal();
for (int i = 0; i < n; i++) {
res = max(res, (p[ap[i]] - p[i]).square());
}
return res;
}
auto getRectangularCover() {
T res = DBL_MAX;
array<Point<T>, 4> pos;
auto ap = getAntiPodal();
for (int i = 0, l = ap[0], r = 0; i < n; i++) {
auto &a = p[i], b = p[(i + 1) % n];
while (dot(b, a, p[l]) < dot(b, a, p[(l + 1) % n])) {
l = (l + 1) % n;
}
while (dot(a, b, p[r]) < dot(a, b, p[(r + 1) % n])) {
r = (r + 1) % n;
}
Line D(a, b);
Line L = D.getVerticalLine(p[l]), R = D.getVerticalLine(p[r]);
Line U = D.getParallelLine(p[ap[i]]);
Point<T> lowleft = intersection(L, D), lowright = intersection(R, D);
Point<T> upleft = intersection(L, U), upright = intersection(R, U);
T length = dist(lowleft, lowright), width = dist(lowleft, upleft);
if (length * width < res) {
res = length * width;
pos = {lowleft, lowright, upright, upleft};
}
}
return pair(res, pos);
}
// run getHull first
friend auto minkowski(Polygon& a, Polygon& b) {
a.norm(), b.norm();
int n = a.p.size(), m = b.p.size();
vector<Point<T>> res;
auto &p = a.p, &q = b.p;
int i = 0, j = 0;
while (i < n or j < m) {
res.push_back(p[i % n] + q[j % m]);
T c = cross(p[(i + 1) % n] - p[i % n], q[(j + 1) % m] - q[j % m]);
i += c >= 0 and i < n;
j += c <= 0 and j < m;
}
Polygon mk(res.size());
swap(mk.p, res);
return mk;
}
friend T dist(Polygon a, Polygon b) {
a.getHull(), b.getHull();
if (polygonIntersectPolygon(a, b))
return 0;
for (auto& p : b.p) {
p = -p;
}
auto mk = minkowski(a, b);
T res = DBL_MAX;
for (int i = 0; i < mk.p.size(); i++) {
Line l(mk.p[i], mk.p[(i + 1) % mk.p.size()]);
res = min(res, l.pointToSegment({}));
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector point(n, Point(0., 0.));
for (auto& [x, y] : point) {
cin >> x >> y;
}
Polygon<double> poly(n);
poly.p = point;
poly.getHull();
constexpr int maxn = 1e6;
vector x(maxn * 2 + 1, 0), y(maxn * 2 + 1, 0);
for (auto& a : poly.p) {
x[a.x + maxn]++;
y[a.y + maxn]++;
}
auto inhull = [&](Point<double> p) {
return x[p.x + maxn] and y[p.y + maxn];
};
Polygon<double> poly1(n);
poly1.p = point;
int ans = 1;
for (int i = 0; i < n; i++) {
if (inhull(point[i]))
continue;
poly1.polarSort(point[i]);
auto point1 = poly1.p;
point1.erase(ranges::find(point1, point[i]));
for (int j = 0; j < n - 1; j++) {
ans += inhull(point1[j]) and inhull(point1[(j + 1) % (n - 1)]);
// cerr << point1[j] << '\n';
}
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 19032kb
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: 18940kb
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: 18960kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 4ms
memory: 18960kb
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: 19028kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Time Limit Exceeded
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...