QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#515366 | #2268. Solar Car | Afterlife# | WA | 1ms | 8344kb | C++14 | 4.1kb | 2024-08-11 17:22:45 | 2024-08-11 17:22:45 |
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;
}
}
}
}
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;i++)
for(int j=0;j<n;j++)
f[i][j]=D[i][j];
for(int i=0;i<n;i++)
for(int j=i;j<n;j++)
f[j][i]=f[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(12)<<ans/(b-a+1)/(d-c+1)<<"\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8344kb
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.000000000000 20.440306508911 20.000000000000 19.000000000000 15.440306508911 21.606571644990
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 6332kb
input:
3 186 689 716 695 247 -231 133 1 2 1 3 1 3 2 2 3 3 2 2 2 2 3 3 1 2 1 2 1 2 3 3 1 3 3 3 2 3 3 3 2 2 3 3 1 3 2 2 1 2 3 3 1 2 2 2 1 1 3 3 1 2 1 2 1 1 1 2 1 2 2 2 3 3 2 3 2 2 2 3 1 3 1 3 2 3 1 3 1 2 1 3 1 2 1 2 1 2 2 2 3 3 1 2 1 2 1 3 2 2 1 2 2 2 1 2 1 2 1 3 1 2 1 3 1 3 2 2 1 3 1 2 3 3 1 3 3 3 2 2 1 3 2...
output:
1702.356810470635 1829.354658422631 1452.054026033667 1452.054026033667 1960.016692983138 1187.037045445630 1483.355782380782 1764.023641142378 1452.054026033667 1829.354658422631 1187.037045445630 2018.004974617113 922.020064857593 1960.016692983138 1902.028411349162 2018.004974617113 1764.02364114...
result:
wrong answer 1st numbers differ - expected: '1810.0252312', found: '1702.3568105', error = '0.0594845'