QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#595782 | #9434. Italian Cuisine | ucup-team4938# | WA | 10ms | 3652kb | C++14 | 2.2kb | 2024-09-28 14:27:31 | 2024-09-28 14:27:32 |
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-1]);
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: 3652kb
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: 3648kb
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: 3648kb
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 5711 5624 1034 2479 3920 4372 2044 4996 5070 2251 4382 4175 1489 1154 3231 4038 1631 5086 14444 1692 6066 687 1512 4849 5456 2757 8341 8557 8235 1013 5203 10853 6042 6300 4480 2303 2728 1739 2187 3385 4266 6322 909 4334 1518 948 5036 1449 2376 3180 4810 1443 1786 47...
result:
wrong answer 2nd numbers differ - expected: '3086', found: '2862'