QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#515220 | #2268. Solar Car | ucup-team052 | WA | 1ms | 6456kb | C++23 | 2.5kb | 2024-08-11 16:09:15 | 2024-08-11 16:09:15 |
Judging History
answer
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define N 2005
#define ll long long
struct Vec
{
int x,y;
Vec(int a=0,int b=0) {x=a,y=b;}
double norm() {return sqrt(1LL*x*x+1LL*y*y);}
};
const double inf=1e100;
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
ll cross(const Vec &x,const Vec &y) {return 1LL*x.x*y.y-1LL*x.y*y.x;}
int sgn(ll x)
{
if(x<0) return -1;
else if(x>0) return 1;
else return 0;
}
int ccw(const Vec &x,const Vec &y,const Vec &z) {return sgn(cross(y-x,z-x));}
Vec a[N];
Vec o(0,0);
int id[N];
int n,ok[N][N];
double dis[N][N],ans[N][N];
void solve(int l,int r)
{
for(int i=l;i<=r;i++)
{
Vec premn=a[id[i%n]],u=a[id[i%n]];
int lst=id[i%n];
for(int j=i-1;j>=l;j--)
{
Vec v=a[id[j%n]];
if(ccw(u,premn,v)==1)
{
dis[id[i%n]][id[j%n]]=dis[id[i%n]][lst]+dis[lst][id[j%n]];
dis[id[j%n]][id[i%n]]=dis[id[i%n]][id[j%n]];
}
else
{
dis[id[i%n]][id[j%n]]=(u-v).norm();
dis[id[j%n]][id[i%n]]=dis[id[i%n]][id[j%n]];
premn=v,lst=id[j%n];
}
}
}
}
signed main() {
#ifdef xay5421
freopen("b.in","r",stdin);
#endif
cin>>n;
for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y;
for(int i=0;i<n;i++) id[i]=i;
sort(id,id+n,[&](int x,int y){
return atan2(a[x].y,a[x].x)<atan2(a[y].y,a[y].x);
});
int pos0=0,pos1=0,pos2=0,pos3=0;
for(int i=0;i<n;i++)
{
double val=atan2(a[id[i]].y,a[id[i]].x);
if(val<=atan2(-1,0)) pos3=i+1;
if(val<=atan2(0,1)) pos2=i+1;
if(val<=atan2(1,0)) pos1=i+1;
}
// for(int i=0;i<n;i++) printf("%d %d\n",a[id[i]].x,a[id[i]].y);
// printf("%d %d %d %d\n",pos0,pos1,pos2,pos3);
solve(pos0,pos2-1);
solve(pos1,pos3-1);
solve(pos2,pos0+n-1);
solve(pos3,pos1+n-1);
for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(dis[i][j]==0) dis[i][j]=(a[i]-a[j]).norm();
// for(int i=0;i<n;i++) for(int j=0;j<n;j++) printf("%2.2lf%c",dis[i][j]," \n"[j==n-1]);
cerr<<clock()<<endl;
for(int i=0;i<n;i++) for(int j=i;j<n;j++)
{
for(int k=0;k<n;k++) ans[i+1][j+1]=max(ans[i+1][j+1],dis[i][k]+dis[j][k]);
ans[j+1][i+1]=ans[i+1][j+1];
}
cerr<<clock()<<endl;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=ans[i][j]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
int Q; cin>>Q;
while(Q--)
{
int l1,r1,l2,r2;
scanf("%d %d %d %d",&l1,&r1,&l2,&r2);
double sum=ans[r1][r2]-ans[l1-1][r2]-ans[r1][l2-1]+ans[l1-1][l2-1];
printf("%.10lf\n",sum/(r1-l1+1)/(r2-l2+1));
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 6456kb
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:
25.3398014455 20.4403065089 19.8994949366 19.0000000000 19.8994949366 23.3485344372
result:
wrong answer 1st numbers differ - expected: '24.0000000', found: '25.3398014', error = '0.0558251'