Guard the empire

The input consists of several test cases.

The first line of each case contains two integers

and

, where $N$ is the number of bone dragon in the ground and $D$ is the distance of coverage of the weapon. Then is followed by $N$ lines each containing two integers

and

, representing the coordinate of the position of each bone dragon.

Then a blank line follows to separate the cases.

The input is terminated by a line containing pair of zeros

C++(g++ 7.5.0) 解法, 执行用时: 17ms, 内存消耗: 480K, 提交时间: 2023-07-01 14:43:23

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

struct que {
	double l, r;
} q[N];

bool cmp(que a, que b)
{
	return a.l < b.l;
}

int main()
{
	int n, d, t = 0;;
	while (cin >> n >> d) {
		if (n == 0 && d == 0) break;
		t++;
		cout << "Case " << t << ": ";
		bool flag = true;
		for (int i = 0; i < n; i++) {

			double x, y; cin >> x >> y;
			if (y <= d) {
				q[i].l = x - sqrt(d * d - y * y);
				q[i].r = x + sqrt(d * d - y * y);
			}
			else flag = false;

		}
		if (flag) {
			sort(q, q + n, cmp);
			double pos = -10000000;
			int ct = 0;

			for (int i = 0; i < n; i++) {
				if (q[i].l <= pos) pos = min(q[i].r, pos);
				else {
					ct++;
					pos = q[i].r;
				}
			}

			cout << ct << '\n';

		} else cout << -1 << '\n';
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 548K, 提交时间: 2019-12-30 11:58:50

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
struct P {
	double l,r;
	bool operator <(const P &t) const {
		if(l!=t.l) return l<t.l;
		return r<t.r;
	}
}p[N];
int main() {
	int n,d,o=0;
	while(~scanf("%d%d",&n,&d),n||d) {
		bool f=false;
		for(int i=0,x,y;i<n;i++) {
			scanf("%d%d",&x,&y);
			if(d<y) f=true;
			if(f) continue;
			p[i].l=x-sqrt(1.0*d*d-1.0*y*y);
			p[i].r=x+sqrt(1.0*d*d-1.0*y*y);
		}
		sort(p,p+n);
		int ans=1;
		double now=p[0].r;
		for(int i=1;i<n;i++) {
			if(p[i].l>now) {
				ans++;
				now=p[i].r;
			}
			else if(p[i].r<now) now=p[i].r;
		}
		printf("Case %d: %d\n",++o,f?-1:ans);
	}
	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 504K, 提交时间: 2019-12-28 21:08:36

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<double,double> P;
P a[1005];
int main()
{
	int n,d,f,ca=1;
	while(cin>>n>>d)
	{
		if(n==0&&d==0)break;
		f=0;
		for(int i=0;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			if(y>d)f=1;
			double z=sqrt(d*d-y*y);
			a[i].first=x-z;
			a[i].second=x+z;
		}
		cout<<"Case "<<ca++<<": ";
		if(f)
		{
			cout<<"-1"<<endl;
			continue;
		}
		sort(a,a+n);
		int cnt=1;double t=a[0].second;
		for(int i=1;i<n;i++)
		{
			if(t>a[i].first)t=min(t,a[i].second);
			else cnt++,t=a[i].second;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

详情