読者です 読者をやめる 読者になる 読者になる

AOJ Problem 0090 : Overlaps of Seals

404 Not Found

円の交点座標を求めてその点を含んでいる円の数をカウントすればいいんだけど、

円の交点座標を求めるのがなかなか大変。三角関数とかベクトルを使わないと恐ろしいことになるっぽい。

ということで、

エクセルを用いた円と円の交点計算

を見つつ交点を出力する関数をつくる。一つ目の落とし穴はC言語atan2は引数がy,xの順番で与えられていること。

二つの目の落とし穴は、解法は恐らくあってるはずなのに、ひたすらWAしか出ないなーと思っていたら『最大値記憶用変数を1で初期化していなかった』(他人に言われて気づいたorz)


WA10回くらい出しましたごめんなさい。

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
struct P{double x,y;};
#define rep(i,n) for(int i=0;i<n;i++)
const double EPS = 1e-15;

vector<P> cross(P a, P b){
	vector<P> ret;
	
	double x = a.x - b.x , y = a.y - b.y;
	double L = x * x + y * y;
	if(L > 4.0)return ret;
	
	L = sqrt(L);
	double C = atan2(b.y-a.y,b.x-a.x);
	double alpha = acos(L/2);
	
	P r1,r2;
	r1.x = a.x + cos(C+alpha) , r1.y = a.y + sin(C+alpha);
	r2.x = a.x + cos(C-alpha) , r2.y = a.y + sin(C-alpha);
	
	ret.push_back(r1) , ret.push_back(r2);
	return ret;
}

bool check(P cir , P pt){
	cir.x -= pt.x , cir.y -= pt.y;
	return (cir.x*cir.x + cir.y * cir.y) <= 1.0 + EPS;
}

int main(){
	int n;
	while(scanf("%d",&n) && n){
		int ret = 1;
		vector<P> data(n);
		rep(i,n)scanf("%lf,%lf\n",&data[i].x,&data[i].y);
		
		vector<P> search;
		rep(i,n){
			for(int j=i+1;j<n;j++){
				vector<P> get = cross(data[i],data[j]);
				rep(k,get.size())search.push_back(get[k]);
			}
		}
		rep(i,search.size()){
			int count = 0;
			rep(j,n)count += check(data[j],search[i]);
			ret = max(ret,count);
		}
		cout << ret << endl;
	}
}