4616708_ce.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<iterator>
using namespace std;
struct point
{
	int x;
	int y;
};
vector<point> island;
point input;
int d;
int n;
int result;
bool ok;
void minsert(point a)
{
	for(vector<point>::iterator count=island.begin();count!=island.end();count++)
	{
		if(a.x==(*count).x)
		{
			(*count).y=(*count).y>a.y?(*count).y:a.y;
			return;
		}
		else if(a.x<(*count).x) {island.insert(count,a);return;}
	}
	island.push_back(a);
}
void checkout()
{
	for(int count=0;count<island.size();count++)
	{
		cout<<island[count].x<<" "<<island[count].y<<endl;
	}
}
void slove(int start)
{
	result++;
	double dis=(double)d;
	double xx,yy;
	double radar=sqrt(dis*dis-(double)island[start].y*island[start].y)
		            +(double)island[start].x;
	for(int count=start+1;count<island.size();count++)
	{
		xx=(double)island[count].x;
		yy=(double)island[count].y;
		if(dis*dis<yy*yy+(radar-xx)*(radar-xx)) break;
		else continue;
	}
	if(count==island.size()) return;
	else slove(count);
}
int main()
{
	int testnumber=0;
	while(cin>>n>>d)
	{
		testnumber++;
		island.clear();
		result=0;
		ok=true;
		if(n==0) return 0;
		int count;
		for(count=0;count<n;count++)
		{
			cin>>input.x>>input.y;
			input.y=abs(input.y);
			if(input.y>d) {ok=false;break;}
			minsert(input);
		}
		if(ok==false) cout<<"Case "<<testnumber<<": "<<-1<<endl;
		else
		{
			slove(0);
			cout<<"Case "<<testnumber<<": "<<result<<endl;
		}
		getchar();
		//checkout();
	}
	return 0;
}