QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#389164#8513. Insects, Mathematics, Accuracy, and EfficiencyinstallbWA 32ms129324kbC++145.2kb2024-04-14 04:04:372024-04-14 04:04:38

Judging History

你现在查看的是最新测评结果

  • [2024-04-14 04:04:38]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:129324kb
  • [2024-04-14 04:04:37]
  • 提交

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'