题面
首先这道题容易想到降维, 一个点P(x, y)能够被圆心O在X轴上的一个圆覆盖, 等价于O在线段[$latex x-\sqrt{r^2-y^2}$, $latex x+\sqrt{r^2-y^2}$]上. 这样就转化为要用最少的点标记所有的区间.
考虑贪心, 根据之前类似区间问题[POJ3190]Stall Reservations[贪心]和[POJ3614]Sunscreen[贪心]的分析, 我们先把这些区间按左端点排序, 依次考虑每个区间, 把雷达(开始位于pos=-inf)尽量往后放, 放在当前能管到的区间最大的一个右端点处; 如果扫到的区间的左端点都比当前能管到的最大的一个右端点(当前雷达位置pos)还靠右, 就新建一个雷达放在这个区间的右端点, 更新pos.
证明类似于[POJ3190]Stall Reservations[贪心].
注意如果有一个点离X轴太远, 要输出无解.
#include<cstdio>
#include<cmath>
#include<algorithm>
#define in inline
#define re register
#define int long long
#define db double
using namespace std;
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
int n,r;
struct segment{
db l,r;
bool operator<(const segment &t){return l<t.l;}
}a[1001];
signed main()
{
int cnt=0;
while(1)
{
int f=0;
++cnt;
n=read(),r=read();
if(!n) break;
for(re int i=1;i<=n;++i)
{
db x,y;
scanf("%lf %lf",&x,&y);
if(y>(db)r){f=1;}
a[i].l=x-sqrt((db)r*(db)r-y*y);
a[i].r=x+sqrt((db)r*(db)r-y*y);
}
if(f){printf("Case %lld: -1\n",cnt);continue;}
sort(a+1,a+n+1);
int ans=0;
db pos=-1e10;//当前雷达位置
for(re int i=1;i<=n;++i)
{
if(a[i].l>pos) pos=a[i].r,++ans;
else pos=pos<a[i].r?pos:a[i].r;
}
printf("Case %lld: %lld\n",cnt,ans);
}
return 0;
}
UPD: 进阶指南上的严谨证明
对于每个区间[a[i].l, a[i].r], 有两种决策: 1 使用已有的点标记它; 2 新建一个点标记它
若选择1, 下一个雷达可以放在任意位置, 但选择2的话必须把一个新的雷达放在区间[a[i].l, a[i].r]内. 决策1的可达状态包含了决策2.
同理, 把雷达尽量往后放这一决策达到的状态, 也包含了放在靠前位置的可达状态.
因此这样的策略不会使后面的决策被制约, 是优秀的.
这种方法叫做 决策包容性.
实际上[POJ3190]Stall Reservations[贪心]也可以这样理解.
CGaZn的博客
最新评论