QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#389164 | #8513. Insects, Mathematics, Accuracy, and Efficiency | installb | WA | 32ms | 129324kb | C++14 | 5.2kb | 2024-04-14 04:04:37 | 2024-04-14 04:04:38 |
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;
return ret;
}
void solve(){
cin >> n >> R;
int debug = 0; if(n == 1604) debug = 1;
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());
int l,r;
for(auto [ang,x] : G){
// cout << ang << ',' << x << endl;
if(x < 0) r = -x - 1;
if(x > 0) l = x - 1;
}
G.push_back({pi,0});
l = (l + 1) % n;
db ans = 0.0,curS = 0.0;
for(int i = l;;i = (i + 1) % n){
curS += 0.5 * det(p[i],p[(i + 1) % n]);
if(i == r) break;
}
curS += 0.5 * det(p[(r + 1) % n],p[l]);
S = 0.0;
for(int i = 0;i < n;i ++) S += 0.5 * det(p[i],p[(i + 1) % n]);
if(debug) cout << S << ' ' << curS << ' ' << l << ',' << r << endl;
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;
}
curS -= 0.5 * det(p[(r + 1) % n],p[l]);
if(cur < 0){
r = (r + 1) % n;
assert(-cur - 1 == r);
curS += 0.5 * det(p[r],p[(r + 1) % n]);
}
if(cur > 0){
curS -= 0.5 * det(p[l],p[(l + 1) % n]);
assert(cur - 1 == l);
l = (l + 1) % n;
}
curS += 0.5 * det(p[(r + 1) % n],p[l]);
}
cout << fixed << setprecision(15) << ans << '\n';
}
int main(){
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 26ms
memory: 129180kb
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: 19ms
memory: 128904kb
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: 28ms
memory: 128912kb
input:
1 100 13 37
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 28ms
memory: 129224kb
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: 16ms
memory: 129204kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.424949238019508
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 24ms
memory: 129196kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.562561766054955
result:
ok found '732310.562561766', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 31ms
memory: 129128kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.595499957939296
result:
ok found '892213.595499958', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 22ms
memory: 129264kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.494464025913544
result:
ok found '619005.494464026', expected '619005.494464026', error '0.000000000'
Test #9:
score: 0
Accepted
time: 31ms
memory: 129300kb
input:
1000 10000 -9998 -136 -9996 -245 -9995 -280 -9993 -347 -9991 -397 -9989 -440 -9985 -525 -9984 -545 -9983 -564 -9981 -599 -9979 -632 -9973 -721 -9971 -747 -9966 -810 -9963 -846 -9957 -916 -9953 -958 -9948 -1008 -9945 -1037 -9938 -1103 -9927 -1196 -9920 -1253 -9913 -1308 -9908 -1346 -9891 -1465 -9874 ...
output:
314026591.780110353836790
result:
ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'
Test #10:
score: 0
Accepted
time: 24ms
memory: 128808kb
input:
2 10000 -9999 0 -9998 -1
output:
12070.567811865475243
result:
ok found '12070.567811865', expected '12070.567811865', error '0.000000000'
Test #11:
score: -100
Wrong Answer
time: 32ms
memory: 129324kb
input:
1604 10000 2604 -9655 7380 -6748 9963 859 9843 1765 -1452 9894 -2024 9793 -8862 4633 -2604 -9655 9301 3673 9871 -1601 -565 -9984 9640 -2659 9312 3645 -8291 -5591 7879 6158 1301 9915 509 9987 7757 -6311 -9301 -3673 7702 -6378 5415 8407 -9971 761 9023 -4311 -6785 7346 -9852 1714 -9788 -2048 9819 -1894...
output:
3.14157e+08 3.14157e+08 0,1603 23.112349928502226
result:
wrong answer 1st numbers differ - expected: '314156571.1123499', found: '314157000.0000000', error = '0.0000014'