QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#595770 | #9434. Italian Cuisine | ucup-team4938# | WA | 10ms | 3724kb | C++14 | 2.2kb | 2024-09-28 14:26:28 | 2024-09-28 14:26:28 |
Judging History
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'