C Guard the empire(2019西南民族大学新生赛)

题目链接
这题我也是服了,我比赛的时候都没发现可以放在实数点上,以为圆心只能在x为整数的点上
算法上就是计算出当前点所能画出的圆心的最左边到最右边的区间之后就是那种线段相交包含的感觉了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,cnt=0;double m,x,y;
while(~scanf("%d%lf",&n,&m))
{
if(n==0&&m==0)
break;
int f=0,ans=1;
pair<double,double> p[10005];
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
if(y>m)
f=1;
double z=sqrt(m*m-y*y);
p[i].first=x-z;
p[i].second=x+z;
}
printf("Case %d: ",++cnt);
if(f) puts("-1");
else
{
sort(p+1,p+1+n);
double jk=p[1].second;
for(int i=2;i<=n;i++)
{
if(jk>p[i].first) jk=min(jk,p[i].second);
else jk=p[i].second,ans++;
}
printf("%d\n",ans);
}
}
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%