题解：CF1817C Similar Polynomials

Red_river · 2025-01-19 16:31:43 · 题解

题目大意

题目中说明，给你一个平面直角坐标系，其中平铺着单位为一的正方形。平面直角坐标系正中间开始放置。求半径为 R 的圆完全覆盖多少个。

题意分析

如图所示，图形差不多就是这样。中间浅色部分就是为 R=2 时的答案。虽然有一点点抽象，还是凑合着看吧。我们不难发现，中间有一个类似于十字架的东西，同时对于其他部分，只用枚举横纵坐标，判断是在圆的内部还是外部，是外部就减一。最后直接用纵坐标统计答案。所以时间复杂度是 O(R) 的。具体可参考代码理解。

CODE

#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define int long long
#define ull unsigned long long
#define ri register int
#define INF 2147483647
#define mod 998244353
#define N 50005
#define NO printf("No\n")
#define YES printf("Yes\n")

using namespace std;
int n,m,k,jk,ans,sum,num,cnt,tot;
int head[N],vis[N],wis[N],f[N];

void read(int &x)
{
    x=0;int ff=1;char ty;
    ty=getchar();
    while(!(ty>='0'&&ty<='9'))
    {
        if(ty=='-') ff=-1;
        ty=getchar();
    }
    while(ty>='0'&&ty<='9')
        x=(x<<3)+(x<<1)+ty-'0',ty=getchar();
    x*=ff;return;
}

void write(int x){
    if(x==0){
        putchar('0');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    char asd[201];int ip=0;
    while(x) asd[++ip]=x%10+'0',x/=10;
    for(int i=ip;i>=1;i--) putchar(asd[i]);
    return;
}

long double dis(long double x, long double y, long double xx, long double yy){
    return (long double) sqrt(1.0*(x-xx)*(x-xx)+1.0*(y-yy)*(y-yy));
}//勾股求距离。

void dg(){
    int x=n-1,y=-1;//中间在坐标轴上的已经算过了，要减一。
    while(y>-n-1&&x){//范围
        while(dis(x+0.5,y-0.5,0.0,0.0)>1.0*n&&x>0) --x;
        //判断如果到原点的距离小于半径，就要减一。
        sum+=x;//加上贡献。
        if(x==0) break;//答案已经没有贡献了。
        --y;//围绕着圆，纵坐标减一。
    }
    return;
}

signed main()
{
    read(n);ans=n*4-3;// 十字架上的答案，还要减去重复的。
    dg();ans+=sum*4;//只算了半个半圆，但因为这部分的答案相同，所以直接乘四。
    wh(ans);
    return 0;
}