Poj 1328: Radar Installation

poj1328.md

Poj 1328: Radar Installation

題目

分析

還是 最少涵蓋區間，但是難了許多，我竟 WA 了七次才 AC。 三個重點：

1. 按每個點對應的圓心 x 坐標排序，而不是每個點的 x 坐標
2. 須先處理不可能的情況（y 坐標 > D）
3. 求對應的圓心 x 坐標時，會有兩個解，應取較大那個。

AC Code

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
	int x, y;
	double center_x;
	
	bool operator<(const Point& p) const {
		return center_x < p.center_x;
	}
};

Point data[1000+1];
int N, D;

double get_center_x(const Point& p) {
	return double(p.x) + sqrt(double(D*D - p.y*p.y));
}

bool in_circle(double x, double y, const Point& p) {
	double dx = double(p.x) - x;
	double dy = double(p.y) - y;
	return (dx*dx + dy*dy <= double(D*D));
}

int solve() {
	// if (D < 0)
	// 	return -1;
	
	for (int i = 0; i < N; i++)
		if (abs(data[i].y) > D)
			return -1;
	
	sort(data, data + N);
	
	int cnt = 0;
	double center_x = data[0].center_x;

	for (int i = 1; i < N; i++) {
		if (in_circle(center_x, 0.0, data[i]))
			continue;
		else {
			cnt++;
			center_x = data[i].center_x;
		}
	}
	cnt++;
	
	return cnt;
}

int main() {
	ios::sync_with_stdio(false);
	
	int case_cnt = 1;
	while (cin >> N >> D) {
		if (N == 0 && D == 0) break;
		
		for (int i = 0; i < N; i++) {
			cin >> data[i].x >> data[i].y;
			data[i].center_x = get_center_x(data[i]);
		}
		
		cout << "Case " << case_cnt++ << ": " << solve() << endl;
	}
	
	return 0;
}