QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515455#2268. Solar CarAfterlife#WA 0ms8400kbC++144.2kb2024-08-11 17:54:212024-08-11 17:54:22

Judging History

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

  • [2024-08-11 17:54:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8400kb
  • [2024-08-11 17:54:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#pragma GCC target("avx2")

#define int long long

const int N=4e3+1e2+7;

const double pi=acos(-1);

int n;

struct P {
    int x,y;
    int id;
    double len()
    {
        return hypot(y,x);
    }
}p[N];
 
P operator -(const P &a,const P &b)
{
    return {a.x-b.x,a.y-b.y};
}

P operator *(const P &a,int b)
{
    return {a.x*b,a.y*b};
}

int sgn(int x)
{
    return x<0?-1:x>0;
}

int det(P a,P b)
{
    return a.x*b.y-a.y*b.x;
}
int dot(P a,P b)
{
    return a.x*a.x+b.y*b.y;
}
bool onseg(const P &u,const P &a,const P &b)
{
    return !sgn(det(a-u,b-u))&&sgn(dot(a-u,b-u))<=0;
}

int ori(const P &a,const P &b,const P &c)
{
    return sgn(det(b-a,c-a));
}

int segment_inter(const P &a,const P &b,const P &c,const P &d)
{
    int d1=ori(a,b,c),d2=ori(a,b,d);
    int d3=ori(c,d,a),d4=ori(c,d,b);
    if(d1*d2<0&&d3*d4<0)
        return 1;
    if((d1==0&&onseg(c,a,b))||(d2==0&&onseg(d,a,b))||(d3==0&&onseg(a,b,c))||(d4==0&&onseg(a,b,d)))
        return 0;
    return 0;
}



double d[N][N],D[N][N];

double fix(double ang)
{
    while(ang<0)
        ang+=2*pi;
    while(ang>2*pi)
        ang-=2*pi;
    return ang;
}

double f[N][N];
int pos[N][N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        // p[i].x=rand()%1000+1,p[i].y=rand()%1000+1;
        cin>>p[i].x>>p[i].y;
        p[i].id=i;
    }
    sort(p,p+n,[&](const P &a,const P &b){
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    });
    for(int i=0;i<n;i++)
    {
        vector<int> st;
        st.push_back(i);
        for(int j=(i+1)%n;j!=i;j=(j+1)%n)
        {
            double ang=atan2(p[j].y,p[j].x)-atan2(p[i].y,p[i].x);
            ang=fix(ang);
            if(ang>pi)
                break;
            while(st.size()>1&&!segment_inter(p[st.end()[-2]],p[j],p[st.back()],p[st.back()]*(int)1e6))
                st.pop_back();
            d[i][j]=d[i][st.back()]+(p[st.back()]-p[j]).len();
            st.push_back(j);
        }
        for(int j=(i-1+n)%n;j!=i;j=(j+n-1)%n)
        {
            double ang=atan2(p[i].y,p[i].x)-atan2(p[j].y,p[j].x);
            ang=fix(ang);
            if(ang>pi)
                break;
            while(st.size()>1&&!segment_inter(p[st.end()[-2]],p[j],p[st.back()],p[st.back()]*(int)1e6))
                st.pop_back();
            d[i][j]=d[i][st.back()]+(p[st.back()]-p[j]).len();
            st.push_back(j);
        }
    }

    for(int i=0;i<n;i++)
        for(int j=i;j<n;j++)
            d[j][i]=d[i][j];
    
    for(int i=0;i<2*n;++i){
        for(int j=0;j<2*n;++j){
            d[i][j]=d[i%n][j%n];
        }
    }
    for(int i=0;i<2*n;++i){
        pos[i][i]=i;
        f[i][i]=0;
    }
    for(int len=2;len<=2*n;++len){
        for(int l=0;l+len-1<2*n;++l){
            int r=l+len-1;
            for(int k=pos[l][r-1];k<=pos[l+1][r];++k){
                double w=d[l][k]+d[k][r];
                if(w>f[l][r]){
                    pos[l][r]=k;
                    f[l][r]=w;
                }
            }
          //  cerr<<" pos: "<<l<<" "<<r<<" "<<pos[l][r]<<" "<<f[l][r]<<endl;
        }
    }
    for(int i=0;i<n<<1;i++)
        for(int j=i;j<n<<1;j++)
            f[j][i]=f[i][j];
    for(int i=0;i<n<<1;i++)
        for(int j=0;j<n<<1;j++){
            int ni=i%n,nj=j%n;
            D[p[ni].id][p[nj].id]=max(f[i][j],D[p[ni].id][p[nj].id]);
        }
            
    for(int i=0;i<n<<1;i++)
        for(int j=0;j<n<<1;j++)
            f[i][j]=D[i][j];
    
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {
            if(i)
                f[i][j]+=f[i-1][j];
            if(j)
                f[i][j]+=f[i][j-1];
            if(i&&j)
                f[i][j]-=f[i-1][j-1];
        }
    int q;
    cin>>q;
    while(q--)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        a--,b--,c--,d--;
        double ans=f[b][d];
        if(a)
            ans-=f[a-1][d];
        if(c)
            ans-=f[c-1][b];
        if(a&&c)
            ans+=f[a-1][c-1];
        cout<<fixed<<setprecision(3)<<ans/(b-a+1)/(d-c+1)<<"\n";
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8400kb

input:

5
7 0
3 3
0 7
-3 3
-7 0
6
1 1 3 3
3 3 4 4
1 1 5 5
5 5 2 2
2 2 4 4
1 5 1 5

output:

24.000
20.440
20.000
19.000
15.440
21.607

result:

wrong answer 2nd numbers differ - expected: '20.4403065', found: '20.4400000', error = '0.0000150'