QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#595724 | #9434. Italian Cuisine | ucup-team4938# | WA | 7ms | 3720kb | C++14 | 2.2kb | 2024-09-28 14:20:38 | 2024-09-28 14:20:39 |
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[i+2]);
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: 3720kb
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: 3708kb
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: 7ms
memory: 3636kb
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:
21442 7355 8112 1214 9528 31067 16100 22221 23035 1771 5705 16684 16306 5797 12553 21859 7765 15800 10576 3230 3196 14505 14624 5822 18762 46314 3024 28461 1525 4229 16499 22071 12326 20004 30717 31623 2898 23808 31895 26341 22020 17700 8409 8871 3591 5850 11263 15948 20246 2715 13863 3247 1985 2151...
result:
wrong answer 1st numbers differ - expected: '5093', found: '21442'