QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362686 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team133# | RE | 0ms | 4376kb | C++23 | 12.0kb | 2024-03-23 16:41:27 | 2024-03-23 16:41:29 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif
#include <type_traits>
namespace geometry {
template <typename T> struct Point {
static T EPS;
static void set_eps(T eps) { EPS = eps; }
T x, y;
Point() {}
Point(T x, T y) : x(x), y(y) {}
Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
Point operator*(T t) const { return Point(x * t, y * t); }
Point operator/(T t) const { return Point(x / t, y / t); }
bool operator==(const Point& p) const { return x == p.x and y == p.y; }
bool operator!=(const Point& p) const { return not((*this) == p); }
bool operator<(const Point& p) const { return x != p.x ? x < p.x : y < p.y; }
friend std::istream& operator>>(std::istream& is, Point& p) { return is >> p.x >> p.y; }
friend std::ostream& operator<<(std::ostream& os, const Point& p) { return os << p.x << ' ' << p.y; }
T norm() { return std::sqrt(x * x + y * y); }
T norm2() { return x * x + y * y; }
T arg() { return std::atan2(y, x); }
T dot(const Point& p) { return x * p.x + y * p.y; }
T det(const Point& p) { return x * p.y - y * p.x; }
Point perp() { return Point(-y, x); }
Point unit() { return *this / norm(); }
Point normal() { return perp().unit(); }
Point rotate(T rad) { return Point(std::cos(rad) * x - std::sin(rad) * y, std::sin(rad) * x + std::cos(rad) * y); }
};
template <> double Point<double>::EPS = 1e-9;
template <> long double Point<long double>::EPS = 1e-12;
template <> int Point<int>::EPS = 0;
template <> long long Point<long long>::EPS = 0;
template <typename T> int sgn(T x) { return x < -Point<T>::EPS ? -1 : x > Point<T>::EPS ? 1 : 0; }
} // namespace geometry
namespace geometry {
enum Position { COUNTER_CLOCKWISE = +1, CLOCKWISE = -1, ONLINE_BACK = +2, ONLINE_FRONT = -2, ON_SEGMENT = 0 };
template <typename T> Position ccw(const Point<T>& a, Point<T> b, Point<T> c) {
b = b - a;
c = c - a;
if (sgn(b.det(c)) == 1) return COUNTER_CLOCKWISE;
if (sgn(b.det(c)) == -1) return CLOCKWISE;
if (sgn(b.dot(c)) == -1) return ONLINE_BACK;
if (b.norm2() < c.norm2()) return ONLINE_FRONT;
return ON_SEGMENT;
}
} // namespace geometry
namespace geometry {
template <typename T> struct Polygon : std::vector<Point<T>> {
using std::vector<Point<T>>::vector;
Polygon(int n) : std::vector<Point<T>>(n) {}
T area2() {
T sum = 0;
int n = this->size();
for (int i = 0; i < n; i++) sum += (*this)[i].det((*this)[i + 1 == n ? 0 : i + 1]);
return sum < 0 ? -sum : sum;
}
T area() { return area2() / 2; }
bool is_convex() {
int n = this->size();
for (int j = 0; j < n; j++) {
int i = (j == 0 ? n - 1 : j - 1), k = (j == n - 1 ? 0 : j + 1);
if (ccw((*this)[i], (*this)[j], (*this)[k]) == CLOCKWISE) return false;
}
return true;
}
};
} // namespace geometry
namespace geometry {
template <typename T> std::vector<int> convex_hull(const std::vector<Point<T>>& P, bool inclusive = false) {
int n = P.size();
if (n == 1) return {0};
if (n == 2) return {0, 1};
std::vector<int> ord(n);
std::iota(begin(ord), end(ord), 0);
std::sort(begin(ord), end(ord), [&](int l, int r) { return P[l] < P[r]; });
std::vector<int> ch(n + 1, -1);
int s = 0, t = 0;
for (int _ = 0; _ < 2; _++, s = --t, std::reverse(begin(ord), end(ord))) {
for (int& i : ord) {
for (; t >= s + 2; t--) {
auto det = (P[ch[t - 1]] - P[ch[t - 2]]).det(P[i] - P[ch[t - 2]]);
if (inclusive ? det >= 0 : det > 0) break;
}
ch[t++] = i;
}
}
return {begin(ch), begin(ch) + t - (t == 2 and ch[0] == ch[1])};
}
} // namespace geometry
namespace geometry {
template <typename T> struct Circle {
Point<T> c;
T r;
Circle() {}
Circle(Point<T> c, T r) : c(c), r(r) {}
friend std::istream& operator>>(std::istream& is, Circle& c) { return is >> c.c >> c.r; }
friend std::ostream& operator<<(std::ostream& os, const Circle& c) { return os << c.c << ' ' << c.r; }
};
} // namespace geometry
namespace geometry {
template <typename T> struct Line {
Point<T> a, b;
Line() {}
Line(const Point<T>& a, const Point<T>& b) : a(a), b(b) {}
// A * x + B * y + C = 0
Line(T A, T B, T C) {}
friend std::istream& operator>>(std::istream& is, Line& l) { return is >> l.a >> l.b; }
friend std::ostream& operator<<(std::ostream& os, const Line& l) { return os << l.a << " to " << l.b; }
};
template <typename T> struct Segment : Line<T> {
Segment() {}
Segment(const Point<T>& a, const Point<T>& b) : Line<T>(a, b) {}
};
} // namespace geometry
namespace geometry {
template <typename T> Point<T> projection(const Line<T>& l, const Point<T>& p) {
Point<T> a = p - l.a, b = l.b - l.a;
return l.a + b * a.dot(b) / b.norm2();
}
} // namespace geometry
namespace geometry {
template <typename T> bool is_parallel(const Line<T>& l, const Line<T>& m) {
return sgn((l.b - l.a).det(m.b - m.a)) == 0;
}
template <typename T> bool is_orthogonal(const Line<T>& l, const Line<T>& m) {
return sgn((l.b - l.a).dot(m.b - m.a)) == 0;
}
template <typename T> bool has_crosspoint(const Segment<T>& s, const Segment<T>& t) {
return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 and ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
template <typename T> int count_common_tangent(const Circle<T>& c, const Circle<T>& d) {
T dist = (c.c - d.c).norm();
int tmp = sgn(dist - (c.r + d.r));
if (tmp > 0) return 4;
if (tmp == 0) return 3;
tmp = sgn(dist - (sgn(c.r - d.r) > 0 ? c.r - d.r : d.r - c.r));
if (tmp > 0) return 2;
if (tmp == 0) return 1;
return 0;
}
template <typename T> Point<T> crosspoint(const Line<T>& l, const Line<T>& m) {
assert(not is_parallel(l, m));
Point<T> u = l.b - l.a, v = m.b - m.a;
return l.a + u * v.det(m.a - l.a) / v.det(u);
}
template <typename T> Point<T> crosspoint(const Segment<T>& s, const Segment<T>& t) {
assert(has_crosspoint(s, t));
if (not is_parallel(s, t)) return crosspoint(Line(s.a, s.b), Line(t.a, t.b));
std::vector<Point<T>> v = {s.a, s.b, t.a, t.b};
for (int i = 0; i <= 2; i++) {
for (int j = 2; j >= i; j--) {
if (v[j + 1] < v[j]) {
std::swap(v[j], v[j + 1]);
}
}
}
return v[1];
}
template <typename T> std::vector<Point<T>> crosspoint(const Circle<T>& c, const Line<T>& l) {
Point<T> h = projection(l, c.c);
T x = c.r * c.r - (c.c - h).norm2();
if (sgn(x) < 0) return {};
if (sgn(x) == 0) return {h};
Point<T> v = (l.b - l.a).unit() * std::sqrt(x);
return {h - v, h + v};
}
template <typename T> std::vector<Point<T>> crosspoint(const Circle<T>& c, const Segment<T>& s) {}
template <typename T> std::vector<Point<T>> crosspoint(const Circle<T>& c1, const Circle<T>& c2) {
T r1 = c1.r, r2 = c2.r;
if (r1 < r2) return crosspoint(c2, c1);
T d = (c2.c - c1.c).norm();
if (sgn(d - (r1 + r2)) > 0 or sgn(d - (r1 - r2)) < 0) return {};
Point<T> v = c2.c - c1.c;
if (sgn(d - (r1 + r2)) == 0 or sgn(d - (r1 - r2)) == 0) return {c1.c + v.unit() * r1};
T p = ((r1 * r1 - r2 * r2) / d + d) / 2, q = std::sqrt(r1 * r1 - p * p);
Point<T> h = c1.c + v.unit() * p;
Point<T> i = v.normal();
return {h + i * q, h - i * q};
}
} // namespace geometry
using namespace std;
typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
template <class T> istream& operator>>(istream& is, vector<T>& v) {
for (auto& x : v) is >> x;
return is;
}
template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
auto sep = "";
for (const auto& x : v) os << exchange(sep, " ") << x;
return os;
}
template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }
template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }
template <class T> void mkuni(vector<T>& v) {
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));
}
template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }
using namespace geometry;
const double PI = acos(-1);
double f(double l, double r, double x) {
if (l < 0) l += 2 * PI;
while (r < l) r += 2 * PI;
while (r - 2 * PI >= l) r -= 2 * PI;
while (x < l) x += 2 * PI;
while (r < x) x -= 2 * PI;
return l <= x and x <= r ? x : -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, R;
cin >> N >> R;
Polygon<double> ps;
for (int i = 0; i < N; i++) {
int X, Y;
cin >> X >> Y;
ps.emplace_back(X, Y);
}
{
auto res = convex_hull(ps);
vector<Point<double>> nps;
for (int& idx : res) nps.emplace_back(ps[idx]);
swap(ps, nps);
N = ps.size();
}
double sum = ps.area(), ans = sum;
Circle<double> C(Point<double>(0, 0), R);
auto calc = [&](int l, int len) -> double {
Line<double> L(ps[l], ps[(l + len) % N]);
auto cross = crosspoint(C, L);
assert(int(cross.size()) == 2);
if (ps[l] != cross[0] and ccw(ps[l], ps[(l + len) % N], cross[0]) != ONLINE_BACK) {
swap(cross[0], cross[1]);
assert(ps[l] == cross[0] or ccw(ps[l], ps[(l + len) % N], cross[0]) == ONLINE_BACK);
}
double start = atan2(cross[0].y, cross[0].x), end = atan2(cross[1].y, cross[1].x);
auto center = (cross[0] + cross[1]) / 2;
Line<double> perp(center, center + (L.b - L.a).perp());
double res = 0;
if (len > 1) {
Line<double> l1(ps[l], ps[(l + 1) % N]);
Line<double> l2(ps[(l + len) % N], ps[(l + len - 1) % N]);
auto cross1 = crosspoint(C, l1);
auto cross2 = crosspoint(C, l2);
assert(int(cross1.size()) == 2);
assert(int(cross2.size()) == 2);
vector<double> a1, a2;
for (auto p : cross1) a1.emplace_back(atan2(p.y, p.x));
for (auto p : cross2) a2.emplace_back(atan2(p.y, p.x));
if (f(start, end, a1[0]) == -1) swap(a1[0], a1[1]);
if (f(start, end, a2[0]) == -1) swap(a2[0], a2[1]);
assert(f(start, end, a1[0]) != -1);
assert(f(start, end, a2[0]) != -1);
if (a1[0] < a2[0]) return -IINF;
start = a2[0], end = a1[0];
}
{
Polygon<double> tmp;
tmp.emplace_back(ps[l]);
tmp.emplace_back(ps[(l + len) % N]);
tmp.emplace_back(cos(start) * R, sin(start) * R);
res = max(res, tmp.area());
}
{
Polygon<double> tmp;
tmp.emplace_back(ps[l]);
tmp.emplace_back(ps[(l + len) % N]);
tmp.emplace_back(cos(end) * R, sin(end) * R);
res = max(res, tmp.area());
}
{
auto cross3 = crosspoint(C, perp);
for (auto p : cross3) {
double x = atan2(p.y, p.x);
if (f(start, end, x) != -1) {
Polygon<double> tmp;
tmp.emplace_back(ps[l]);
tmp.emplace_back(ps[(l + len) % N]);
tmp.emplace_back(p);
res = max(res, tmp.area());
}
}
}
return res;
};
for (int i = 0; i < N; i++) {
double sub = 0;
for (int j = 1; j < N; j++) {
if (j > 1) {
Polygon<double> tmp;
tmp.emplace_back(ps[i]);
tmp.emplace_back(ps[(i + j - 1) % N]);
tmp.emplace_back(ps[(i + j) % N]);
sub += tmp.area();
}
ans = max(ans, sum + calc(i, j) - sub);
}
}
cout << fixed << setprecision(15);
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4300kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.000000000000000
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4200kb
input:
2 100 17 7 19 90
output:
4849.704644437563729
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
1 100 13 37
output:
0.000000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4376kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000.000000000000000
result:
ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4336kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.424949237960391
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: -100
Runtime Error
input:
4 1000 200 -600 600 -400 800 -600 0 -800