8
19
2014
0

Codeforces Round#230C

题意:

你可以叉掉某些点,使这些点不连通。给定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;
}
Category: codeforces | Tags: 数学

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com