QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363251#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team135#WA 1ms4068kbC++204.0kb2024-03-23 19:58:162024-03-23 19:58:17

Judging History

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

  • [2024-03-23 19:58:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4068kb
  • [2024-03-23 19:58:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
#define y1 rtgerf
#define tm hytgrfgef
#define pt pair<int,int>
#define x first
#define y second
#define Point pt
double dist (Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int sign(int x) {
    if (x == 0)
        return 0;
    else if (x < 0)
        return -1;
    else
        return 1;
}

bool cmp (Point a, Point b) {
    return a.x < b.x || a.x == b.x && a.y < b.y;
}
int sq (Point a, Point b, Point c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool cw (Point a, Point b, Point c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}

bool ccw (Point a, Point b, Point c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}

void convex_hull (vector<Point> & a) {
    if (a.size() == 1)  return;
    sort (a.begin(), a.end(), &cmp);
    Point p1 = a[0],  p2 = a.back();
    vector<Point> up, down;
    up.push_back (p1);
    down.push_back (p1);
    for (size_t i=1; i<a.size(); ++i) {
        if (i==a.size()-1 || cw (p1, a[i], p2)) {
            while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
                up.pop_back();
            up.push_back (a[i]);
        }
        if (i==a.size()-1 || ccw (p1, a[i], p2)) {
            while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
                down.pop_back();
            down.push_back (a[i]);
        }
    }
    a.clear();
    for (size_t i=0; i<up.size(); ++i)
        a.push_back (up[i]);
    for (size_t i=down.size()-2; i>0; --i)
        a.push_back (down[i]);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,r;cin>>n>>r;if(n==1) {cout<<0;return 0;}
    vector<pt> a(n);for(int i=0;i<n;++i) {cin>>a[i].x>>a[i].y;} convex_hull(a); n=a.size(); if(n==1) {cout<<0;return 0;}
    int vals[2*n]={0};for(int i=0;i<2*n;++i) {vals[i]=(a[i%n].x*a[(i+1)%n].y-a[i%n].y*a[(i+1)%n].x);}
    int pr[2*n+1]={0};for(int i=0;i<2*n;++i) {pr[i+1]=pr[i]+vals[i];}
    double res=0;
    for(auto h:a) debug(h.x,h.y);
    auto f1=[&](int i,int j)->double
    {
        if(j<i) {j+=n;}
        int have=pr[j]-pr[i];
        int add=(a[j%n].x*a[i%n].y-a[j%n].y*a[i%n].x);
        double ans=abs(have+add)/2.0;
        debug(i,j,have,add,ans);
        return ans;
    };
    auto f2=[&](pt u,pt v,pt w)->double
    {
        double answ=0;
        double len=dist(u,v);
        pt o=pt(0,0);
        double h=(abs(sq(u,v,o)))/len;
        if(sq(u,v,w)*sq(u,v,o)>=0)
        {
            answ=max(answ,len*(r-h)/2.0);
        }
        if(sq(u,v,w)*sq(u,v,o)<=0)
        {
            answ=max(answ,len*(r+h)/2.0);
        }
        return answ;
    };
    auto f=[&](int i,int j)
    {
        if(i==j) return;
        debug(i,j);
        res=max(res,f1(i,j)+f2(a[i],a[j],a[(i+1)%n]));
        res=max(res,f1(j,i)+f2(a[i],a[j],a[(j+1)%n]));
    };
    for(int i=0;i<n;++i)
    {
        int low=1;int up=n;
        while(up-low>2)
        {
            int l1=(2*low+up)/3;int r1=(low+2*up)/3;
            int vall=abs(sq(a[i],a[(i+1)%n],a[(i+l1)%n]));int valr=abs(sq(a[i],a[(i+1)%n],a[(i+r1)%n]));
            if(vall<valr) {up=r1;} else {low=l1;}
        }
        int cur=low;
        for(int j=low+1;j<up;++j)
        {
            if(abs(sq(a[i],a[(i+1)%n],a[(i+j)%n]))<abs(sq(a[i],a[(i+1)%n],a[(i+cur)%n])))
            {
                cur=j;
            }
        }
        for(int i1:{i%n,(i+1)%n,(i+n-1)%n})
            {
                for(int j1:{cur%n,(cur+1)%n,(cur+n-1)%n})
            {
                f(i1,j1);
            }
            }
    }
    cout<<setprecision(25)<<res;
    return 0;
}
/*
3 5
5 0
-5 0
3 4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4040kb

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:

2000000

result:

ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

2 100
17 7
19 90

output:

4849.704644437563729297835

result:

ok found '4849.704644438', expected '4849.704644438', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

1 100
13 37

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 4068kb

input:

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

output:

2240000

result:

ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.424949238076806068

result:

ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

732310.5625617660116404295

result:

ok found '732310.562561766', expected '732310.562561766', error '0.000000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

4 1000
-600 700
-300 900
0 800
-800 400

output:

892213.595499957911670208

result:

ok found '892213.595499958', expected '892213.595499958', error '0.000000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 4052kb

input:

5 1000
-300 -200
-200 -400
-100 -700
-800 -500
-500 -300

output:

619005.4944640259491279721

result:

ok found '619005.494464026', expected '619005.494464026', error '0.000000000'

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 4012kb

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:

314026171.5

result:

wrong answer 1st numbers differ - expected: '314026591.7801104', found: '314026171.5000000', error = '0.0000013'