QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515220#2268. Solar Carucup-team052WA 1ms6456kbC++232.5kb2024-08-11 16:09:152024-08-11 16:09:15

Judging History

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

  • [2024-08-11 16:09:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6456kb
  • [2024-08-11 16:09:15]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'