QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369693 | #8513. Insects, Mathematics, Accuracy, and Efficiency | willow# | WA | 1ms | 4748kb | C++17 | 6.7kb | 2024-03-28 16:33:08 | 2024-03-28 16:33:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9, pi = acos(-1);
int Dcmp(double x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
double Sqr(double x) {
return x * x;
}
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
bool operator < (const Point &rhs) const {
return Dcmp(x - rhs.x) == 0 ? Dcmp(y - rhs.y) < 0 : Dcmp(x - rhs.x) < 0;
}
Point operator + (const Point &rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
double operator * (const Point &rhs) const {
return x * rhs.x + y * rhs.y;
}
double operator ^ (const Point &rhs) const {
return x * rhs.y - y * rhs.x;
}
Point operator * (const double &k) const {
return Point(x * k, y * k);
}
Point operator / (const double &k) const {
return Point(x / k, y / k);
}
double len2() {
return x * x + y * y;
}
double len() {
return sqrt(len2());
}
Point Unit() {
return *this / len();
}
Point Rotate90() {
return Point(-y, x);
}
};
int Left(Point a, Point b, Point c) {
return Dcmp((b - a) ^ (c - a)) >= 0;
}
double Area(Point a, Point b, Point c) {
return fabs((c - a) ^ (b - a)) / 2;
}
Point base;
vector<Point> Convex(vector<Point> a) {
int n = a.size(), cnt = 0;
if(n < 3)
return a;
base = a[0];
for(auto p : a) if(p < base) base = p;
sort(a.begin(), a.end(), [](const Point &a, const Point &b) {
int d = Dcmp((a - base) ^ (b - base));
return d ? d > 0 : Dcmp((a - base).len() - (b - base).len()) < 0;
});
vector<Point> res;
for(int i = 0; i < n; ++ i) {
while(cnt > 1 && Left(res[cnt - 2], a[i], res[cnt - 1]))
-- cnt, res.pop_back();
res.push_back(a[i]), ++ cnt;
}
return res;
}
struct Line {
Point s, t;
Line(Point s = Point(), Point t = Point()) : s(s), t(t) {}
};
double DisToLine(Line l, Point p) {
Point v1 = l.t - l.s, v2 = p - l.s;
return fabs(v1 ^ v2) / v1.len();
}
Point LineInter(Line l1, Line l2) {
double a1 = (l2.t - l2.s) ^ (l1.s - l2.s), a2 = (l2.t - l2.s) ^ (l1.t - l2.s);
return (l1.s * a2 - l1.t * a1) / (a2 - a1);
}
Point LineVer(Line l, Point p) {
Point v = l.t - l.s;
v = v.Rotate90();
return LineInter(l, Line(p, p + v));
}
struct Circle {
Point c;
double r;
Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
};
vector<Point> LineInterCircle(Line a, Circle b) {
if(Dcmp(DisToLine(a, b.c) - b.r) > 0)
return vector<Point>();
if(Dcmp(DisToLine(a, b.c) - b.r) == 0)
return {LineVer(a, b.c)};
double x = sqrt(Sqr(b.r) - Sqr(DisToLine(a, b.c)));
Point o = LineVer(a, b.c);
return {o - (a.t - a.s).Unit() * x, o + (a.t - a.s).Unit() * x};
}
int n, r;
vector<Point> p;
const int maxn = 2e4 + 5;
double le[maxn], ri[maxn];
Point cp[maxn];
vector<pair<double, int> > op;
set<int> s;
double Calc(double al, double ar, Point a, Point b) {
// cerr << "Get Calc(" << al << ", " << ar << ") P(" << a.x << ", " << a.y << ") P(" << b.x << ", " << b.y << ")" << endl;
for(int i = 1; i <= 100; ++ i) {
double ml = al + (ar - al) / 3, mr = ar - (ar - al) / 3;
Point pl = Point(r * cos(ml), r * sin(ml)), pr = Point(r * cos(mr), r * sin(mr));
if(Dcmp(Area(a, b, pl) - Area(a, b, pr)) > 0)
ar = mr;
else
al = ml;
}
Point pl = Point(r * cos(al), r * sin(al)), pr = Point(r * cos(ar), r * sin(ar));
return max(Area(a, b, pl), Area(a, b, pr));
}
int main() {
scanf("%d%d", &n, &r);
for(int i = 1, x, y; i <= n; ++ i) {
scanf("%d%d", &x, &y);
p.push_back(Point(x, y));
}
if(n == 1) {
puts("0.0");
return 0;
}
auto c = Convex(p);
int m = c.size();
double area = 0;
for(int i = 0; i < m; ++ i) {
int j = (i + 1) % m;
area += Area(c[0], c[i], c[j]);
auto in = LineInterCircle(Line(c[i], c[j]), Circle(Point(0, 0), r));
assert(in.size() == 2u);
double al = atan2(in[0].y, in[0].x), ar = atan2(in[1].y, in[1].x);
if(Dcmp(al - ar) > 0)
al -= 2 * pi;
cp[i] = c[i];
le[i] = al;
ri[i] = ar;
}
// cerr << "Fuck" << endl;
for(int i = 0; i < m; ++ i) {
cp[i + m] = cp[i];
le[i + m] = le[i] + 2 * pi;
ri[i + m] = ri[i] + 2 * pi;
}
for(int i = 0; i < 2 * m; ++ i) {
op.push_back({le[i], -(i + 1)});
op.push_back({ri[i], i + 1});
}
// cerr << "?????" << endl;
sort(op.begin(), op.end());
int sop = op.size();
double nowa = 0, ans = area;
for(int i = 0; i < sop; ) {
int j = i;
while(j < sop && Dcmp(op[i].first - op[j].first) == 0) {
// cerr << op[j].first << " " << op[j].second << endl;
if(op[j].second < 0) { // add
int q = -(op[j].second + 1);
// cerr << "Add " << q << endl;
if(s.size() > 0) {
int w = *s.begin();
nowa += Area(cp[w], cp[q], cp[(q + 1) % (2 * m)]);
}
s.insert(q);
}
else {
int q = op[j].second - 1;
// cerr << "Del " << q << endl;
if(s.size() > 0) {
int w = *prev(s.end());
nowa -= Area(cp[q], cp[(q + 1) % (2 * m)], cp[(w + 1) % (2 * m)]);
}
s.erase(s.find(q));
}
// cerr << "? " << j << endl;
++ j;
}
// cerr << "Fuck " << i << " " << j << endl;
assert(s.size());
if(*s.begin() >= m) {
break;
}
// cerr << "Set: ";
// for(auto x : s)
// cerr << x << " ";
// cerr << endl;
double mx = Calc(op[i].first, op[j].first, cp[*s.begin()], cp[(*prev(s.end()) + 1) % (2 * m)]);
// cerr << area << " " << mx << " " << nowa << " " << area + mx - nowa << endl;
ans = max(ans, area + mx - nowa);
i = j;
}
printf("%.15f\n", ans);
}
/*
Fuck
?????
-3.14159 -1
Add 0
? 0
Fuck 0 1
Set: 0
Get Calc(-3.14159, -1.5708) P(0, 0) P(1, 0)
2e+06 1 0 2e+06
-1.5708 1
Del 0
? 1
-1.5708 -2
Add 1
? 2
Fuck 1 3
Set: 1
Get Calc(-1.5708, -1.13687e-16) P(1, 0) P(2, 0)
2e+06 1 0 2e+06
-1.13687e-16 2
Del 1
? 3
0 -3
Add 2
? 4
Fuck 3 5
Set: 2
Get Calc(-1.13687e-16, 3.14159) P(2, 0) P(3, 0)
2e+06 1 0 2e+06
3.14159 -4
Add 3
? 5
3.14159 3
Del 2
? 6
Fuck 5 7
2000001.000000000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4556kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
1999999.999999998137355
result:
ok found '1999999.999999998', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4556kb
input:
2 100 17 7 19 90
output:
4849.704644436478702
result:
ok found '4849.704644436', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4132kb
input:
1 100 13 37
output:
0.0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 4748kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2039999.999999998137355
result:
wrong answer 1st numbers differ - expected: '2240000.0000000', found: '2040000.0000000', error = '0.0892857'