P12813

035966_L3 · 2025-07-13 19:58:37 · 题解

预热：http://8.136.99.126/p/P83

• 按 x 轴方向切片后 y=a+c 那一片上点数是 f(R,c)-f(L,c)，其中 f(p,q)=\begin{cases}0,&p>q\\2\lfloor\sqrt{p^2-q^2}\rfloor+1,&p \le q\end{cases}
• 按 y 轴方向切片后 x=b+c 那一片上点数是 f(R,c)-f(L,c)
• 按 x 轴方向切片后每片上所有点的 y 坐标平均值是 b
• 按 y 轴方向切片后每片上所有点的 x 坐标平均值是 a

于是我们在 2s / 2M 之内成功 AC 了本题！

AC Code：

#include <bits/stdc++.h>
using namespace std;
int c[10012],f1[10012],f2[10012];
long long f3[10012],f4[10012];
namespace INPUT_SPACE{const int S=(1<<20)+5;char B[S],*H,*T;inline int gc() { if(H==T) T=(H=B)+fread(B,1,S,stdin);return (H==T)?EOF:*H++; }inline int inn() { int x,ch,f=1;while((ch=gc())<'0'||ch>'9')if(ch=='-')f=-1;x=ch^'0';while((ch=gc())>='0'&&ch<='9') x=x*10+(ch^'0');return x*f; }}using INPUT_SPACE::inn;
inline int get(int r1,int r2)
{
    if(r2>r1) return 0;
    int d=sqrtl(r1*r1-r2*r2+0.4);
    return 2*d+1;
}
int main()
{
    c[0]=1;
    for(int i=-5000;i<=5000;i++)
        for(int j=-5000;j<=5000;j++)
        {
            if(i==0&&j==0) continue;
            c[(int)ceill(sqrtl(i*i+j*j-0.4))]++;
        }
    for(int i=1;i<=5000;i++)
        c[i]+=c[i-1];
    int n=inn(),a1=inn(),a2=inn(),a3=a1,a4=a1,a5=a2,a6=a2;
    f1[a1+5006]=f2[a2+5006]=1,f3[a1+5006]=a2,f4[a2+5006]=a1;
    puts("NIE");
    for(int ii=2;ii<=n;ii++)
    {
        int x=inn(),y=inn();
        a3=min(a3,x),a4=max(a4,x),a5=min(a5,y),a6=max(a6,y);
        f1[x+5006]++,f2[y+5006]++,f3[x+5006]+=y,f4[y+5006]+=x;
        if(a4-a3==a6-a5&&(a4-a3)%2==0)
        {
            int l=0,r=(a4-a3)/2-1;
            while(l<r)
            {
                int mid=(l+r)/2;
                if(c[mid]<c[(a4-a3)/2]-ii) l=mid+1;
                else r=mid;
            }
            if(c[r]==c[(a4-a3)/2]-ii)
            {
                bool ok=true;
                for(int i=a3;i<=a4;i++)
                {
                    if(get((a4-a3)/2,abs((a4+a3)/2-i))-get(r,abs((a4+a3)/2-i))!=f1[i+5006]) ok=false;
                    if(f3[i+5006]!=1ll*f1[i+5006]*(a6+a5)/2) ok=false;
                }
                for(int i=a5;i<=a6;i++)
                {
                    if(get((a6-a5)/2,abs((a6+a5)/2-i))-get(r,abs((a6+a5)/2-i))!=f2[i+5006]) ok=false;
                    if(f4[i+5006]!=1ll*f2[i+5006]*(a4+a3)/2) ok=false;
                }
                if(ok) puts("TAK");
                else puts("NIE");
            }
            else puts("NIE");
        }
        else puts("NIE");
    }
    return 0;
}