题解：P14433 [JOISC 2013] JOI 海报 / JOI Poster

n \le 50

，很小。所以可以使用暴力枚举四个点。

使用一个函数计算

a,b

两点之间的距离，记为

jl(a,b)

。

当大圆包含小圆时，大圆的半径要大于等于小圆的半径加两圆的圆心距离，即

jl(A,B)\ge jl(C,D)+jl(A,C)

。这是一个判断条件。

当一个圆在地图范围内的时候，圆心的两个轴的坐标要大于等于它的半径。它的两个轴的坐标加上半径要小于等于地图两个轴上的大小。即

x_A \ge jl(A,B),x_A \le w-jl(A,B),y_A \ge jl(A,B),y_A\le h-jl(A,B)

，另一个圆同理。

满足这两个条件，答案就加一。

code

CPP

#include<bits/stdc++.h>
using namespace std;
int x[60];
int y[60];
double jl(int a1,int a2){
	int dx=x[a1]-x[a2],dy=y[a1]-y[a2];
	return sqrt(dx*dx+dy*dy);
}
int main(){
	int n,w,h;
	cin>>n>>w>>h;
	for(int i=0;i<n;i++){
		cin>>x[i]>>y[i];
	}
	int sum=0;
	for(int a=0;a<n;a++){
		for(int b=0;b<n;b++){
			if(a==b)continue;
			for(int c=0;c<n;c++){
				if(c==a||c==b)continue;
				for(int d=0;d<n;d++){
					if(d==a||d==b||d==c)continue;
					double r1=jl(a,b),r2=jl(c,d),ac=jl(a,c);
					if(r1>r2+ac+1e-9){
						if(x[a]>=r1&&x[a]<=w-r1&&y[a]>=r1&&y[a]<=h-r1){
							if(x[c]>=r2&&x[c]<=w-r2&&y[c]>=r2&&y[c]<=h-r2){
								sum++;
							}
						}
					}
				}
			}
		}
	}
	cout<<sum;
}

题解：P14433 [JOISC 2013] JOI 海报 / JOI Poster

文章操作

code

相关推荐

评论

题解：P14433 [JOISC 2013] JOI 海报 / JOI Poster