UVa 12537 Radiation

題意：
　　在核能廠半徑範圍內的住家可以得到protective equipments，a和c區域可以得到一組，而b區域因為在重疊範圍內，所以有2組，但在範圍外的d區域沒有equipment，但因為equipments只要1組就夠用了，因此b區域的住家可以分給d區域的住家，題目求d區域在b區域給了equipments之後還有幾戶住家沒有equipments，即為(d-b)。
　　給定一堆點座標和兩個圓心座標，每次兩個圓都有不同的半徑，題目所求為在圓外面點的數量減掉在左圓且在右圓內點的數量，為(d-b)。

想法：

• 找出在左圓範圍內點的數量(a+b)
• 找出在右圓範圍內點的數量(c+b)
• 所有點的總數N=a+b+c+d
• 所求即為N-(a+b)-(c+b) = d-b

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	int N,x[200001],y[200001];
	double a_dis[200001],b_dis[200001];
	int ax,ay,bx,by,Q,R1,R2;
	int BS (int R,double dis[])
	{
	int left = 0, right = N-1;
	while (left != right){
	int mid = (left+right+1)/2;
	if (dis[mid] > R) right = mid-1;
	else left = mid;
	}
	return left+1; //回傳為數量，因此是index+1
	}
	int main()
	{
	freopen ("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; i++) scanf("%d %d",&x[i],&y[i]);
	scanf("%d %d %d %d %d",&ax,&ay,&bx,&by,&Q);
	for (int i=0; i<N; i++) {
	a_dis[i] = sqrt (pow(x[i]-ax,2) + pow(y[i]-ay,2));
	b_dis[i] = sqrt (pow(x[i]-bx,2) + pow(y[i]-by,2));
	}
	sort (a_dis,a_dis+N);
	sort (b_dis,b_dis+N);
	printf("Case %d:\n",Case++);
	while (Q--){
	scanf("%d %d",&R1,&R2);
	int ans = N - BS(R1,a_dis) - BS(R2,b_dis);
	if (ans >= 0) printf("%d\n",ans);
	else printf("0\n");
	}
	}
	return 0;
	}

view raw UVa 12537 Radiation.cpp hosted with ❤ by GitHub