QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#595536#9434. Italian Cuisineucup-team4938#WA 3ms3896kbC++141.7kb2024-09-28 13:56:022024-09-28 13:56:03

Judging History

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

  • [2024-09-28 13:56:03]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3896kb
  • [2024-09-28 13:56:02]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define mod 998244353ll
#define pii pair<int,int>
#define fi first
#define se second
#define mems(x,y) memset(x,y,sizeof(x))
using namespace std;
const int maxn=200010;
const int inf=1e18;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch-48);ch=getchar();}
	return x*f;
}
bool Mbe;

int n,x,y,c;
pii a[maxn];
int calc(pii a,pii b,pii c){
	return abs(a.fi*b.se+b.fi*c.se+c.fi*a.se-a.fi*c.se-b.fi*a.se-c.fi*b.se);
}
bool chk(pii u,pii v,int x,int y,int r){
	int a=v.se-u.se,b=u.fi-v.fi,c=-a*u.fi-b*u.se;
	return (__int128)(a*x+b*y+c)*(a*x+b*y+c)>(__int128)r*r*(a*a+b*b);
}
int get(pii a,pii b,pii c){
	b.fi-=a.fi,b.se-=a.se,c.fi-=a.fi,c.se-=a.se;
	return b.fi*c.se-b.se*c.fi;
}
int ans;
void work(){
	n=read();x=read(),y=read(),c=read();ans=0;
	for(int i=1;i<=n;i++)a[i]=a[i+n]={read(),read()};
	for(int i=1,j=2,sum=0;i<=n;i++){
		while(j<=2*n){
			if(!chk(a[i],a[j],x,y,c))break;
			if(j>i+1){
			// cout<<i<<" "<<j<<" "<<get(a[i],{x,y},a[j])<<" "<<get(a[i],{x,y},a[j-1])<<"\n";
				if((__int128)get(a[i],{x,y},a[j])*get(a[i],{x,y},a[j-1])<=0)break;
			}
			if(j>i+1)sum+=calc(a[i],a[j-1],a[j]);
			j++;
		}
		ans=max(ans,sum);
		// cout<<i<<" "<<j<<" "<<sum<<"\n";
		if(j>i+2)sum-=calc(a[i],a[i+1],a[i+2]);
		if(i+1==j)j++;
	}
	printf("%lld\n",ans);
}

// \
444

bool Med;
int T;
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	
//	cerr<<(&Mbe-&Med)/1048576.0<<" MB\n";
	
	T=read();
	while(T--)work();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3772kb

input:

3
5
1 1 1
0 0
1 0
5 0
3 3
0 5
6
2 4 1
2 0
4 0
6 3
4 6
2 6
0 3
4
3 3 1
3 0
6 3
3 6
0 3

output:

5
24
0

result:

ok 3 number(s): "5 24 0"

Test #2:

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

input:

1
6
0 0 499999993
197878055 -535013568
696616963 -535013568
696616963 40162440
696616963 499999993
-499999993 499999993
-499999993 -535013568

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 3896kb

input:

6666
19
-142 -128 26
-172 -74
-188 -86
-199 -157
-200 -172
-199 -186
-195 -200
-175 -197
-161 -188
-144 -177
-127 -162
-107 -144
-90 -126
-87 -116
-86 -104
-89 -97
-108 -86
-125 -80
-142 -74
-162 -72
16
-161 -161 17
-165 -190
-157 -196
-154 -197
-144 -200
-132 -200
-128 -191
-120 -172
-123 -163
-138...

output:

21442
7355
8112
1214
9528
31067
16100
22221
23035
1771
5705
16684
16306
5797
12553
21859
7765
15800
10576
3230
3196
14505
14624
5822
18762
46314
3024
28461
1525
4229
16499
22071
12326
20004
30717
31623
2898
23808
31895
26341
22020
17700
8409
8871
3591
5850
11263
15948
20246
2715
13863
3247
1985
2151...

result:

wrong answer 1st numbers differ - expected: '5093', found: '21442'