QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#873135 | #9434. Italian Cuisine | Godwang | WA | 12ms | 5712kb | C++23 | 4.4kb | 2025-01-26 09:47:13 | 2025-01-26 09:47:14 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#include<list>
#define double __int128
#define ll __int128
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define lowbit(x) ((x)&(-x))
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a) % mod; //% mod
a = (a * a) % mod; //% mod
n >>= 1;
}
return ans;
}
inline void write(__int128 x)
{
if (x > 9)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
struct Point
{
double x,y;
Point()
{
}
Point(double x,double y):x(x),y(y)
{
}
Point operator + (Point B)
{
return Point(x+B.x,y+B.y);
}
Point operator - (Point B)
{
return Point(x-B.x,y-B.y);
}
bool operator == (Point B)
{
return x-B.x==0&&y-B.y==0;
}
bool operator < (Point B)
{
return x-B.x<0||(x-B.x==0&&y-B.y<0);
}
};
typedef Point Vector;
double Cross(Vector A,Vector B)//叉积
{
return A.x*B.y-A.y*B.x;
}
int Convex_hull(Point *p,int n,Point *ch)
{
n=unique(p,p+n)-p;
sort(p,p+n);
int v=0;
for(int i=0;i<n;i++)
{
while (v>1&&Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])<=0)
{
v--;
}
ch[v++]=p[i];
}
int j=v;
for(int i=n-2;i>=0;i--)
{
while (v>j&&Cross(ch[v-1]-ch[v-2],p[i]-ch[v-1])<=0)
{
v--;
}
ch[v++]=p[i];
}
if(n>1)
{
v--;
}
return v;
}
int dir[4][2] =
{
{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 左右上下
// int dir[8][2]={
// {-1, 0}, {0, 1}, {1, 0}, {0, -1},{-1,-1},{-1,1},{1,-1},{1,1}
// };
const ll mod1 = 998244353ll, P1 = 131, mod2 = 1e9 + 7ll, P2 = 13331;
ll inverse(ll x)
{
return fastpow(x,mod1-2,mod1);
}
const int N = 1e6 + 10, M = 1e6 + 10;
///////////////////////////////////
int tt;
int n;
Point p[N],ch[N],c;
ll R;
///////////////////////////////////
inline ll read()
{
ll 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*10+ch-'0',ch=getchar();
return x*f;
}
///////////////////////////////////
void init()
{
}
///////////////////////////////////
int main()
{
// freopen("ain.txt", "r", stdin); freopen("aout.txt", "w", stdout);
cin>>tt;
while (tt--)
{
n=read();
c.x=read();
c.y=read();
R=read();
rep(i,0,n-1)
{
p[i].x=read();
p[i].y=read();
}
int v=Convex_hull(p,n,ch);
ll ans=0;
int r=1,rr=2;
ll S=0;
rep(leftt,0,v-1)
{
while (1)
{
rr=(r+1)%v;
ll temp=Cross(c-ch[rr],ch[leftt]-ch[rr]);
if(temp<0)
{
break;
}
ll dis=(ch[leftt].x-ch[rr].x)*(ch[leftt].x-ch[rr].x)+(ch[leftt].y-ch[rr].y)*(ch[leftt].y-ch[rr].y);
if(Cross(ch[leftt]-ch[rr],c-ch[rr])*Cross(ch[leftt]-ch[rr],c-ch[rr])<dis*R*R)
{
break;
}
S+=Cross(ch[leftt]-ch[rr],ch[r]-ch[rr]);
ans=max(ans,S);
r=rr;
}
int nxtleftt=(leftt+1)%v;
S-=Cross(ch[leftt]-ch[r],ch[nxtleftt]-ch[r]);
}
write(ans);
putchar('\n');
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 5712kb
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: 5708kb
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: 5708kb
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 3086 2539 668 3535 7421 4883 5711 5624 1034 2479 3920 4372 2044 4996 4569 2251 4382 4175 1489 1154 3231 4038 1631 5086 14444 1692 6066 687 1512 4849 5456 2675 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 46...
result:
wrong answer 16th numbers differ - expected: '5070', found: '4569'