QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#873135#9434. Italian CuisineGodwangWA 12ms5712kbC++234.4kb2025-01-26 09:47:132025-01-26 09:47:14

Judging History

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

  • [2025-01-26 09:47:14]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:5712kb
  • [2025-01-26 09:47:13]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'