【hihocoder】1237 : Farthest Point 微软2016校招在线笔试题

题目：给定一个圆，要你求出一个在里面或者在边上的整数点，使得这个点到原点的距离最大，如果有多个相同，输出x最大，再输出y最大。

思路：对于一个圆，里面整点个数的x是能确定的。你找到x的上下界就可以了。就是mix = ceil(x0-r)//因为是小的值，所以要向上取整。mxx=floor(x0+r)//大的值要向下取整

对于y。我们也能用欧股定理确定。y也是有一个范围。但是并不是所有y都要枚举的。明显。y的值是离圆心越远越好。所以对于每一个x而言只需要枚举最远的两个y值

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

double xo,yo,r;

double dist(double xx1,double yy1,double xx2,double yy2)

{

    return sqrt((xx1-xx2)*(xx1-xx2) + (yy1-yy2)*(yy1-yy2));

}

double eps = 1e-;

bool big (double a,double b)

{

    return (a-b)>eps;

}

bool same (double a,double b)

{

    return fabs(a-b)<eps;

}

void work ()

{

    int mix = (int)ceil(xo-r);

    int mxx = (int)floor(xo+r);

    double mxdis=-;

    int ansx,ansy;

    for (int i=mix;i<=mxx;++i)

    {

        int yy = (int)floor((yo+sqrt(r*r-(i-xo)*(i-xo))));

        double tdis = dist(i,yy,xo,yo);

        if (big(tdis,mxdis))

        {

            mxdis = tdis; ansx = i; ansy = yy;

        }

        else if (same(tdis,mxdis)&&i>ansx)

        {

            mxdis = tdis; ansx = i; ansy = yy;

        }

        else if (same(tdis,mxdis)&&i==ansx&&yy>=ansy)

        {

            mxdis = tdis; ansx = i; ansy = yy;

        }

        yy = (int)ceil(yo-sqrt(r*r-(i-xo)*(i-xo)));

        tdis=dist(i,yy,xo,yo);

        if (big(tdis,mxdis))

        {

            mxdis = tdis; ansx = i; ansy = yy;

        }

        else if (same(tdis,mxdis)&&i>ansx)

        {

            mxdis = tdis; ansx = i; ansy = yy;

        }

        else if (same(tdis,mxdis)&&i==ansx&&yy>=ansy)

        {

            mxdis = tdis; ansx = i; ansy = yy;

        }

    }

    printf ("%d %d\n",ansx,ansy);

    return ;

}

int main()

{

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    while(~scanf("%lf%lf%lf",&xo,&yo,&r)) work();

    return ;

}

巴特西

【hihocoder】1237 : Farthest Point 微软2016校招在线笔试题

最新文章

热门文章