QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515208#2268. Solar Carucup-team052WA 1ms6480kbC++232.5kb2024-08-11 16:02:322024-08-11 16:02:32

Judging History

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

  • [2024-08-11 16:02:32]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6480kb
  • [2024-08-11 16:02:32]
  • 提交

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].x,a[x].y)<atan2(a[y].x,a[y].y);
	});
	int pos0=0,pos1=0,pos2=0,pos3=0;
	for(int i=0;i<n;i++)
	{
		double val=atan2(a[id[i]].x,a[id[i]].y);
		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++) printf("%2.2lf%c",dis[i][j]," \n"[j==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();
	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: 100
Accepted
time: 1ms
memory: 6396kb

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.0000000000
20.4403065089
20.0000000000
19.0000000000
15.4403065089
21.6065716450

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 6480kb

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:

1810.0252312113
1829.3546584226
1452.0540260337
1452.0540260337
1960.0166929831
1510.0423076676
1698.6926238621
1764.0236411424
1452.0540260337
1829.3546584226
1510.0423076676
2018.0049746171
1568.0305893016
1960.0166929831
1902.0284113492
2018.0049746171
1764.0236411424
1764.0236411424
1772.9143620...

result:

ok 133 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 6448kb

input:

3
995 866
-744 999
-528 -207
133
1 2 2 3
2 3 2 3
1 2 2 3
1 2 1 3
1 2 3 3
2 2 2 2
1 3 1 3
3 3 3 3
1 1 2 3
3 3 3 3
1 3 1 1
1 1 3 3
1 2 2 3
2 3 1 2
1 3 1 1
3 3 2 3
1 1 2 3
2 3 1 3
1 2 1 3
1 1 2 2
1 3 1 3
1 1 1 2
1 1 3 3
1 3 1 1
2 2 1 2
2 2 1 3
1 2 1 3
1 2 2 3
2 3 2 2
1 3 1 2
1 2 2 3
1 3 2 3
2 3 1 2
1 3...

output:

3288.1857950114
3607.1024393287
3288.1857950114
3327.8342392698
3288.1857950114
3488.1571065535
3363.2694219717
3726.0477721038
3028.7418170817
3726.0477721038
3261.1771354224
2969.2691506942
3288.1857950114
3288.1857950114
3261.1771354224
3666.5751057163
3028.7418170817
3414.3155652464
3327.8342392...

result:

ok 133 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 6396kb

input:

3
-630 864
896 -31
-359 -691
133
1 3 1 2
1 2 1 2
2 3 2 3
1 2 2 2
1 3 1 3
2 3 2 2
1 3 1 3
1 2 1 1
1 2 1 1
1 2 2 2
1 1 1 3
1 2 1 2
2 2 1 2
2 2 2 3
2 2 2 2
3 3 1 2
1 1 3 3
2 3 1 2
3 3 1 2
1 2 2 3
2 2 2 3
1 2 3 3
2 3 1 3
2 3 2 3
1 2 1 3
1 2 1 3
3 3 2 3
3 3 2 3
2 3 1 3
1 2 1 2
2 3 1 3
3 3 2 2
2 3 1 2
1 2...

output:

3267.2975601703
3267.2975601703
3347.5339322107
3267.2975601703
3255.0284613357
3442.8630629865
3255.0284613357
3267.2975601703
3267.2975601703
3267.2975601703
3240.5521028235
3267.2975601703
3267.2975601703
3442.8630629865
3538.1921937622
3267.2975601703
3187.0611881298
3267.2975601703
3267.2975601...

result:

ok 133 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 6396kb

input:

7
342 -176
53 -703
-687 -627
-580 -95
741 -873
249 47
125 -989
133
2 3 7 7
1 6 1 2
3 6 2 5
4 5 5 7
6 7 3 3
2 4 2 3
1 4 2 5
1 6 1 5
4 5 3 5
1 4 3 3
1 4 1 7
6 7 1 4
3 7 4 5
6 7 2 5
1 5 1 7
1 2 4 6
6 6 1 2
1 3 1 6
3 7 5 7
1 3 1 5
3 7 3 6
2 6 2 5
1 5 2 4
3 4 1 5
3 5 1 2
4 7 3 7
5 7 1 3
3 6 2 6
2 6 2 6
2...

output:

2123.5654111090
2157.7662599915
2486.7414907458
2518.4688725726
2347.0683758134
2368.4242335419
2383.9799238214
2365.0580037650
2551.1004855317
2576.9537396779
2309.5957367223
2227.3389482150
2535.6024323304
2336.3983736128
2349.3367058682
2289.8413315992
2087.1114824953
2272.0273840338
2423.4235397...

result:

ok 133 numbers

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 6400kb

input:

7
105 906
969 -998
68 -422
154 -468
558 785
-849 652
-949 181
133
4 7 2 5
1 6 5 7
5 6 2 7
4 5 4 6
1 4 1 6
2 2 5 7
4 5 4 5
4 6 4 6
6 7 1 6
2 3 3 5
5 7 3 5
6 7 1 6
1 4 3 7
1 6 1 7
3 5 7 7
1 2 2 7
2 5 1 2
4 5 4 5
4 5 3 4
1 6 1 2
5 7 1 2
1 4 1 5
1 5 2 4
4 4 6 7
5 7 2 4
4 4 5 6
3 6 1 4
1 5 5 5
6 7 5 6
3 ...

output:

3419.2323653778
3812.2374749971
3817.7880621641
3368.6827761322
3511.1669182155
3523.7489861640
3124.9801152153
3648.2796487240
3922.0112834559
3390.0738425731
3482.0587339734
3922.0112834559
3420.2688398067
3640.1971568362
3541.9374879458
3822.5463704346
3785.7492931594
3124.9801152153
2934.7040796...

result:

wrong answer 1st numbers differ - expected: '3419.3706440', found: '3419.2323654', error = '0.0000404'