QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#598633#9434. Italian Cuisineucup-team4508#WA 12ms5708kbC++231.2kb2024-09-28 22:42:272024-09-28 22:42:30

Judging History

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

  • [2024-09-28 22:42:30]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:5708kb
  • [2024-09-28 22:42:27]
  • 提交

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'