4624976_wa.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 108 行

#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
#include<iterator>
using namespace std;
struct interval
{
	double left;
	double right;
};
interval island[1005];
int length;
double ix,iy;
double d;
int n;
int result;
bool ok;
interval getinterval(double x,double y)
{
	interval temp;
	temp.left=x-sqrt(d*d-y*y);
	temp.right=x+sqrt(d*d-y*y);
	return temp;
}
void ninsert(interval a,int place)
{
	for(int count=length-1;count>=place;count--)
	{
		island[count+1].left=island[count].left;
		island[count+1].right=island[count].right;
	}
	island[place].left=a.left;
	island[place].right=a.right;
	length++;
}
void check_insert(interval a)
{
	int here=-1;
	for(int count=0;count<length;count++)
	{
		if(a.left<=island[count].left)
		{
			if(a.right>=island[count].right) return;//不能插入
			else 
			{
				if(here==-1) here=count;//记录插入位置
			}
		}
		else 
		{
			if(a.right<island[count].right)//替换
			{
				island[count].left=a.left;
				island[count].right=a.right;
				return ;
			}
		}
		if(a.right<=island[count].left) break;//剪枝
	}
	if(here==-1) here=0;
	ninsert(a,here);
}
void slove()
{
	int count=0;
	while(count<length)
	{
		result++;
		int i;
		for(i=count+1;i<length;i++)
		{
			if(island[i].left<=island[count].right) continue;
			else break;
		}
		count=i;
	}
}
int main()
{
	int testnumber=0;
	while(cin>>n>>d)
	{
		testnumber++;
		length=0;
		result=0;
		ok=true;
		if(n==0) return 0;
		int count;
		interval input;
		for(count=0;count<n;count++)
		{
			cin>>ix>>iy;
			iy=abs(iy);
			if(iy>d) {ok=false;}
			input=getinterval(ix,iy);
			check_insert(input);
		}
		if(ok==false) cout<<"Case "<<testnumber<<": "<<-1<<endl;
		else
		{
			slove();
			cout<<"Case "<<testnumber<<": "<<result<<endl;
		}
		getchar();
	}
	return 0;
}