QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515455 | #2268. Solar Car | Afterlife# | WA | 0ms | 8400kb | C++14 | 4.2kb | 2024-08-11 17:54:21 | 2024-08-11 17:54:22 |
Judging History
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'