QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#389156#8513. Insects, Mathematics, Accuracy, and EfficiencyinstallbWA 27ms130408kbC++144.9kb2024-04-14 03:40:592024-04-14 03:40:59

Judging History

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

  • [2024-04-14 03:40:59]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:130408kb
  • [2024-04-14 03:40:59]
  • 提交

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]);
    curS += 0.5 * det(p[r],p[(r + 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){
            r = (r + 1) % n;
            curS += 0.5 * det(p[r],p[(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: 24ms
memory: 130056kb

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: 27ms
memory: 130408kb

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: 20ms
memory: 129948kb

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: 15ms
memory: 129812kb

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

480000.000000000000000

result:

wrong answer 1st numbers differ - expected: '2240000.0000000', found: '480000.0000000', error = '0.7857143'