tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 1239: Viva Confetti

待ち受ける大きな罠 (誤差)に気を取られていると足元(添え字)がおろそかになるんじゃ。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
long double x[110];
long double y[110];
long double r[110];
const long double EPS = 1e-20;
const long double INF = 1e+20;
const long double PI = acos(-1);
// 今回はlong doubleを使いました。
Pt p[110];
bool oth;
int n;
bool chk(int a,int b,int c,Pt d){
	if(a!=b&&a!=c&&(p[a]-d).ABS()>r[a])return false;
	oth=true;
	for(int i=a+1;i<n;i++){
		if(i==b||i==c)continue;
		if((p[i]-d).ABS()<r[i])return false;
	}
//	printf("%d %d %d %Lf %Lf\n",a,b,c,d.x,d.y);
	return true;
}
int main(){
	int a;
	while(scanf("%d",&a),a){
		n=a;
		for(int i=0;i<a;i++)scanf("%Lf%Lf%Lf",x+i,y+i,r+i);
		for(int i=0;i<a;i++)p[i]=Pt(x[i],y[i]);
		int ret=0;
		vector<Pt> v;
		for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
			long double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
			if(d>r[i]-r[j]&&d<r[i]+r[j]){
				pair<Pt,Pt> tmp=pCC(p[i],r[i],p[j],r[j]);
				v.push_back(tmp.first);
				v.push_back(tmp.second);
			}
		}
		for(int i=0;i<a;i++){
			bool dame=false;
			
			for(int j=i+1;j<a;j++){
				if(i==j)continue;
				long double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
				if(d<r[j]-r[i])dame=true;
			}
			if(dame)continue;
		//	printf("%d ",i);
			oth=false;
			for(int j=i;j<a;j++)for(int k=j+1;k<a;k++){
				long double d=(p[k]-p[j]).ABS();
			//	printf("%d %d %d: %.20Lf\n",i,j,k,d);
				if(d>r[k]-r[j]&&d<r[k]+r[j]){
					pair<Pt,Pt> tmp=pCC(p[j],r[j],p[k],r[k]);
					if(chk(i,j,k,tmp.first)||chk(i,j,k,tmp.second)){
					//	printf("%d: %d %d %Lf %Lf %Lf %Lf\n",i,j,k,tm);
						ret++;
						goto owari;
					}
				}
			}
			owari:;
			if(!oth)ret++;
		}
		printf("%d\n",ret);
	}
}

やばげな誤差制約にするんだったら入力を整数で与えるべきだと思うんですが…