自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:18:10，当前版本为作者最后更新于2025-07-13 19:58:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

$2 \times 10^7 \le n \le 2.5 \times 10^7$，30s，8M，太离谱了！让我们扔掉脑子，开始乱搞。

注意到 $\text{Donut}(a,b,L,R)$ 一定满足：

• 总点数一定是 $\text{CF933D}(R)-\text{CF933D}(L)$（This is CF933D）
• 在 $x$ 轴和 $y$ 轴方向用游标卡尺卡出来的直径一定是 $2R$，且卡到的点是 $(a-R,b),(a+R,b),(a,b-R),(a,b+R)$
• 按 $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;
}