QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#389153 | #8513. Insects, Mathematics, Accuracy, and Efficiency | installb | WA | 36ms | 129200kb | C++14 | 4.9kb | 2024-04-14 03:36:48 | 2024-04-14 03:36:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
const db eps = 1e-12;
const db pi = acos(-1.0);
const int N = 2000005;
int sgn(db x){
if(x > -eps && x < eps) return 0;
if(x > 0) return 1;
return -1;
}
struct point{
db x,y;
point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {}
bool operator < (const point &p) const{
if(sgn(x - p.x) == 0) return sgn(y - p.y) < 0;
return x < p.x;
}
};
point operator - (const point &p1,const point &p2){
return point(p1.x - p2.x,p1.y - p2.y);
}
point operator + (const point &p1,const point &p2){
return point(p1.x + p2.x,p1.y + p2.y);
}
point operator * (db x,const point &p){
return point(x * p.x,x * p.y);
}
db dot(point p1,point p2){
return p1.x * p2.x + p1.y * p2.y;
}
db det(point p1,point p2){
return p1.x * p2.y - p2.x * p1.y;
}
struct line{
point a,b;
line() : a(), b() {}
line(point _a,point _b) : a(_a), b(_b) {}
};
struct circle{
point o; db r;
circle() : o(), r() {}
circle(point _o,db _r) : o(_o), r(_r) {}
};
db len(point p1){
return sqrt(p1.x * p1.x + p1.y * p1.y);
}
db distp(point x,line y){
return fabs(det(y.a - x,y.b - x)) / len(y.b - y.a);
}
point project_point(point x,line y){
point v = y.b - y.a;
return y.a + (dot(v,x - y.a) / dot(v,v)) * v;
}
void sec_line_circle(line x,circle y,point* ret){
db dis = distp(y.o,x);
point pj = project_point(y.o,x);
db l = sqrt(y.r * y.r - dis * dis);
ret[0] = pj - (l / len(x.b - x.a)) * (x.b - x.a);
ret[1] = pj + (l / len(x.b - x.a)) * (x.b - x.a);
}
int stk[N],tp = 0;
void convex_hull(point* ps,int n,point* ret,int &rtc){
sort(ps + 1,ps + 1 + n);
tp = 0; rtc = 0; stk[++ tp] = 1;
for(int i = 2;i <= n;i ++){
while(tp >= 2 && det(ps[stk[tp]] - ps[stk[tp - 1]],ps[i] - ps[stk[tp]]) <= 0) tp --;
stk[++ tp] = i;
}
for(int i = 1;i < tp;i ++) ret[++ rtc] = ps[stk[i]];
tp = 0; stk[++ tp] = n;
for(int i = n - 1;i >= 1;i --){
while(tp >= 2 && det(ps[stk[tp]] - ps[stk[tp - 1]],ps[i] - ps[stk[tp]]) <= 0) tp --;
stk[++ tp] = i;
}
for(int i = 1;i < tp;i ++) ret[++ rtc] = ps[stk[i]];
ret[0] = ret[rtc];
}
int n; db R;
point p[N],q[N];
db S;
db calc(int l,int r,db ang,db curS){
point pi = point(R * cos(ang),R * sin(ang));
db ret = len(p[r] - p[l]) * distp(pi,line(p[l],p[r])) / 2.0 - curS + S;
// cout << l << ' ' << r << ' ' << ang << ' ' << curS << ' ' << ret << '\n';
return ret;
}
void solve(){
cin >> n >> R;
for(int i = 1;i <= n;i ++) cin >> p[i].x >> p[i].y;
int m; convex_hull(p,n,q,m);
for(int i = 1;i <= m;i ++) p[i - 1] = q[i];
n = m;
if(n < 2){
cout << 0.0 << '\n';
return;
}
if(n == 2){
db h = distp(point(0,0),line(p[0],p[1])) + R;
cout << fixed << setprecision(15) << 0.5 * h * len(p[1] - p[0]) << '\n';
return;
}
vector <pair <db,int> > G;
for(int i = 0;i < n;i ++){
point ps[2];
sec_line_circle(line(p[i],p[(i + 1) % n]),circle(point(0,0),R),ps);
db angl = atan2(ps[0].y,ps[0].x);
db angr = atan2(ps[1].y,ps[1].x);
G.push_back({angl,i + 1});
G.push_back({angr,-(i + 1)});
}
sort(G.begin(),G.end());
G.push_back({pi,0});
int l,r;
for(auto [ang,x] : G){
// cout << ang << ',' << x << endl;
if(x > 0) r = x - 1;
else l = x - 1;
}
l = (l + 1) % n;
db ans = 0.0,curS = 0.0;
for(int i = l;i != r;i = (i + 1) % n) curS += 0.5 * det(p[i],p[(i + 1) % n]);
S = 0.0;
for(int i = 0;i < n;i ++) S += 0.5 * det(p[i],p[(i + 1) % n]);
for(int i = 0;i < G.size();i ++){
db al = (i == 0 ? -pi : G[i - 1].first),ar = G[i].first;
int cur = G[i].second;
if(!((r + 1) % n == l)){
r = (r + 1) % n;
ans = max({ans,calc(l,r,al,curS),calc(l,r,ar,curS)});
point ps[2];
sec_line_circle(line(p[l],p[r]),circle(point(0,0),R),ps);
db angl = atan2(ps[0].y,ps[0].x);
db angr = atan2(ps[1].y,ps[1].x);
db mid = (angl < angr ? (angl + angr) / 2.0 : (angl + angr + 2.0 * pi) / 2.0);
if(mid > pi) mid -= 2.0 * pi;
if(mid < -pi) mid += 2.0 * pi;
if(al <= mid && mid <= ar) ans = max(ans,calc(l,r,mid,curS));
r = (r + n - 1) % n;
// cout << "ANGLE " << angl << ',' << angr << ',' << " MID = " << mid << ' ' << al << ',' << ar << ' ' << l << ',' << r << endl;
}
if(cur > 0){
curS += 0.5 * det(p[r],p[(r + 1) % n]);
r = (r + 1) % n;
}
if(cur < 0){
curS -= 0.5 * det(p[l],p[(l + 1) % n]);
l = (l + 1) % n;
}
}
cout << fixed << setprecision(15) << ans << '\n';
}
int main(){
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 23ms
memory: 129132kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.000000000000114
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 16ms
memory: 128828kb
input:
2 100 17 7 19 90
output:
4849.704644437563741
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 12ms
memory: 128876kb
input:
1 100 13 37
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: -100
Wrong Answer
time: 36ms
memory: 129200kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
960000.000000000000057
result:
wrong answer 1st numbers differ - expected: '2240000.0000000', found: '960000.0000000', error = '0.5714286'