QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#363240#8513. Insects, Mathematics, Accuracy, and Efficiencyucup-team135#WA 0ms4016kbC++203.8kb2024-03-23 19:52:032024-03-23 19:52:03

Judging History

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

  • [2024-03-23 19:52:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4016kb
  • [2024-03-23 19:52:03]
  • 提交

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;
        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;
            }
        }
        f(i,cur);f(cur,i);
    }
    cout<<setprecision(25)<<res;
    return 0;
}

詳細信息

Test #1:

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

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: 3844kb

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: 3888kb

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: 3844kb

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: 3800kb

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: -100
Wrong Answer
time: 0ms
memory: 3908kb

input:

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

output:

540000

result:

wrong answer 1st numbers differ - expected: '732310.5625618', found: '540000.0000000', error = '0.2626079'