首页 > 代码库 > 外星人的供给站(贪心)

外星人的供给站(贪心)

为了照到点Point(x0,y0),圆心可以在一个范围内移动,我们设该范围为(x,y)
(Vec[i].x,Vec[i].y)表示第如果圆心在这个范围内,则第i个点就一定能照到,
sum表示为了能照到前i个点,最靠近右边的圆的边界坐标。

#define LOCAL
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
int const MAX_N=101;
typedef struct Point{
    double x,y;
    bool operator<(const Point &other) const
    {
        return x<other.x;
    };
};
Point Vec[MAX_N];
int N,R,K,x,y;
void solve()
{
    int coun=0,i;
    double sum;
    scanf("%d%d",&N,&R);
    for(i=0;i<N;i++)
    {
        scanf("%d%d",&x,&y);
        double temp=sqrt(R*R-y*y);
        Vec[i].x=x-temp;
        Vec[i].y=x+temp;
    }
       std::sort(Vec,Vec+N);
       sum=Vec[0].y;
       coun=1;
       for(i=1;i<N;i++)
    {
        if(sum<Vec[i].x)
        {
                coun++;
                sum=Vec[i].y;
        }
        else
        {
            if(sum>Vec[i].y)
            {
                //最靠近右边的圆的边界坐标为sum时,能照到前i-1个点。如果sum>Vec[i].y,则为了照到i点sum必须减小(此次是关键,不妨用心想一想)                sum=Vec[i].y;

}
} } printf(
"%d\n",coun); } int main() { #ifdef LOCAL freopen("710.in","r",stdin); freopen("710.out","w",stdout); #endif scanf("%d",&K); while(K--) { solve(); } return 0; }