题解 P3737 【[HAOI2014]遥感监测】

PiCaHor · 2018-05-26 23:05:51 · 题解

感觉楼上写麻烦了，这道题还是蛮经典的。首先如果从坐标出发的话显然太麻烦了，所以不妨反一下我们从每一个点出发，从坐标轴上找到能覆盖的这个点的最左的和最右的点（放遥感）。然后就变成了统计点数使得所有的线段都被覆盖--最小点覆盖
至于这个直接贪一下就好了

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read()
{
  int x=0,f=1;
  char c=getchar();
  while(c<'0' || c>'9')
  {
    if(c=='-') f=-1;
    c=getchar();
  }
  while(c<='9' && c>='0')
  {
    x=(x<<3)+(x<<1)+c-'0';
    c=getchar();
  }
  return x*f;
}

const double eps = 1e-6;
int n,r;

struct node
{
  double l,r;
} e[110];
int len;

inline void cal(int x,int y)
{
  double deta;
  deta=sqrt(r*r-y*y);
  e[++len].l=x*1.0-deta;
  e[len].r=x*1.0+deta;
}

bool cmp(node x,node y)
{
  return x.r<y.r;
}

int ans;
double loc;

int main()
{
  n=read(),r=read();
  for(re int i=1; i<=n; ++i)
  {
    int x=read(),y=read();
    cal(x,y);
  }

  sort(e+1,e+len+1,cmp);
  loc=e[1].r;
  ++ans;
  for(re int i=2; i<=len; ++i)
    if(loc+eps<e[i].l) ans++,loc=e[i].r;
  printf("%d\n",ans);
  return 0;
}