题意:
你可以叉掉某些点,使这些点不连通。给定n,问至少要叉多少点,可以使离原点欧几里得距离(平时说的距离)在n之内的整点与比n
距离大的整点都不四联通。
第一遍题意读过去有点难懂。。。我也解释的不是很清楚。。。自己动手画一下就知道了。
实际上画了你就会发现,其实就是画一个意原点为圆心,半径为n的圆。然后做到里面的整点和外面的整点不四联通就行。
那么只要涂掉里面相对最外层的所有整点即可。。。因为斜边(半径)确定,只要枚举一下直角边即可(枚举一条,另一条可以确
定)
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<cmath> #include<cstdlib> #define ll long long #define maxn 100010 #define inf 1000000000 #define linf (1LL<<50) using namespace std; 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*=10;x+=ch-'0';ch=getchar();} return x*f; } inline void read(char *s,int &ts) { char x=getchar(); while(!(x>='a'&&x<='z'))x=getchar(); while(x>='a'&&x<='z')s[++ts]=x,x=getchar(); } int main() { ll n; ll last=0,ans=0; scanf("%I64d",&n); if(n==0) puts("1"); else { for(ll d=n;d>=0;d--) { ll r=(ll)sqrt(n*n-d*d)+(ll)1; //printf("%I64d\n",r); ans+=max((ll)1,r-last); last=r; } ans=(ll)4*ans-(ll)4; printf("%I64d\n",ans); } return 0; }