QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#598625#9434. Italian Cuisineucup-team4508#WA 13ms7752kbC++231.2kb2024-09-28 22:40:322024-09-28 22:40:34

Judging History

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

  • [2024-09-28 22:40:34]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:7752kb
  • [2024-09-28 22:40:32]
  • 提交

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'