QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#598625 | #9434. Italian Cuisine | ucup-team4508# | WA | 13ms | 7752kb | C++23 | 1.2kb | 2024-09-28 22:40:32 | 2024-09-28 22:40:34 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<vector>
using ll=long long;
const int sz=1e5+10;
ll x[sz<<1],y[sz<<1],sum[sz<<1];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin>>t;
while(t--){
int n;
ll a,b,rad;
std::cin>>n>>a>>b>>rad;
for(int i=1;i<=n;i++)std::cin>>x[i]>>y[i],x[n+i]=x[i],y[n+i]=y[i];
a-=x[1],b-=y[1];
for(int i=n*2;i>=1;i--)x[i]-=x[1],y[i]-=y[1];
std::reverse(x+1,x+2*n+1);
std::reverse(y+1,y+2*n+1);
auto judge=[&](int l,int r){
ll A=y[r]-y[l],B=x[l]-x[r],C=x[r]*y[l]-x[l]*y[r];
return __int128(A*a+B*b+C)*(A*a+B*b+C)>(__int128)rad*rad*(A*A+B*B);
};
auto check=[&](int l,int r){
ll A=x[r],B=y[l]-y[r];
return A*b-B*a>=0;
};
for(int i=2;i<=2*n;i++)sum[i]=sum[i-1]+x[i-1]*y[i]-x[i]*y[i-1];
ll ans=0;
for(int l=1,r=3;l<=n;l++){
r=std::max(r,l+2);
while(r<=2*n&&judge(l,r)&&judge(l,r))r++;
if(r>=l+2&&judge(l,r-1))ans=std::max(ans,std::abs(sum[r-1]-sum[l]+x[r-1]*y[l]-x[l]*y[r-1]));
}
std::cout<<ans<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7748kb
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: 1ms
memory: 5704kb
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: 13ms
memory: 7752kb
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 2862 2539 668 3535 7421 4883 10757 13089 1034 4974 3920 4372 2044 4996 5070 2251 4382 4175 1489 1154 3231 12364 1631 5086 25218 1692 6066 2381 1512 4849 5456 2757 14238 8557 18465 1877 11759 17426 12398 11813 4480 2303 2728 1739 2187 3385 4266 12406 909 4334 1518 948 13832 1449 2376 3180 4810 1...
result:
wrong answer 2nd numbers differ - expected: '3086', found: '2862'