English appre:
an infinite straight line：一条无限长的直线
on the coasting：在海岸线上
Cartesian coordinate system,
题目地址：http://poj.org/problem?id=1328
我的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; struct dao
{
double x,y;
}da[10000];
bool cmp(dao a,dao b)
{
return (a.y<b.y)||(a.y==b.y && a.x>b.x);
} int main()
{
int n,d;
double x1,y1;
int k=0;
while(~scanf("%d%d",&n,&d)&&(n||d))
{
int ans=1;
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&x1,&y1);
da[i].x=x1-sqrt((double)d*(double)d-(double)y1*y1);
da[i].y=x1+sqrt((double)d*(double)d-(double)y1*y1);
if((d-y1)<0||d<=0) ans=-1;
} if(ans==-1)
{
printf("Case %d: -1\n",++k);
continue;
}
else
{
sort(da,da+n,cmp);
double t1=da[0].y;
for(int i=1;i<n;i++)
if(da[i].x>t1)//要是用=号，有些数据不可通过。
{
ans++;
t1=da[i].y;//更新右范围
}
printf("Case %d: %d\n",++k, ans);
}
}
}