QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#598633 | #9434. Italian Cuisine | ucup-team4508# | WA | 12ms | 5708kb | C++23 | 1.2kb | 2024-09-28 22:42:27 | 2024-09-28 22:42:30 |
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)&&check(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: 5708kb
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: 5700kb
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: 12ms
memory: 5648kb
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 2172 2539 646 3535 7421 4597 10757 5284 161 2479 3777 4372 2044 2278 5070 2009 2589 4175 655 1104 2570 9610 1631 4530 24626 935 5029 687 1512 4849 5456 2757 2274 3288 8235 744 4199 17069 12398 6300 4480 2038 2668 1739 1211 3385 3271 10907 909 4334 1518 948 4940 1268 1765 2530 4790 823 1786 3022...
result:
wrong answer 2nd numbers differ - expected: '3086', found: '2172'