QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#595770#9434. Italian Cuisineucup-team4938#WA 10ms3724kbC++142.2kb2024-09-28 14:26:282024-09-28 14:26:28

Judging History

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

  • [2024-09-28 14:26:28]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3724kb
  • [2024-09-28 14:26:28]
  • 提交

answer

#include<bits/stdc++.h>
#define int __int128
#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;
}
inline void write(__int128 x){static char buf[100];static int len=-1;if(x<0)putchar('-'),x=-x;do buf[++len]=x%10,x/=10;while(x);while(len>=0)putchar(buf[len--]+48);}

bool Mbe;

int n,x,y,c;
pii a[maxn];
int aabs(int x){
	if(x>0)return x;
	return -x;
}
int calc(pii a,pii b,pii c){
	return aabs(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,__int128 x,__int128 y,__int128 r){
	__int128 a=v.se-u.se,b=u.fi-v.fi,c=-a*u.fi-b*u.se;
	// cout<<a<<" "<<b<<" "<<c<<" "<<(a*u.fi+b*u.se+c==0)<<" "<<(a*v.fi+b*v.se+c==0)<<"\n";
	// int dis=(__int128)(a*x+b*y+c)*(a*x+b*y+c)/(a*a+b*b);
	// write(a*x+b*y+c),putchar(' '),write(a*a+b*b),puts("");
	// cout<<dis<<"\n";
	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;
			// cout<<i<<" "<<j<<"\n";
			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[j]);
		if(i+1==j)j++;
	}
	write(ans);puts("");
}

// \
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: 3724kb

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: 3640kb

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: 10ms
memory: 3640kb

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:

5093
2068
1511
390
2104
5777
3887
4842
4552
409
1642
2597
1826
1319
1216
5070
2251
3225
2502
598
496
3231
3594
864
4865
14744
161
3814
200
627
3084
5097
1423
4875
4555
7008
744
4744
9606
5655
4947
3497
1715
1030
576
1457
2444
3620
3752
901
3633
592
64
3092
1305
654
3087
4184
815
598
4657
1379
887
35...

result:

wrong answer 2nd numbers differ - expected: '3086', found: '2068'