AOJ0090

問題:Overlaps of Seals
半径1のシールが重なっている枚数の最大を求める問題．
接触している場合(中心どうしの距離が２)の場合も重なっているとみなす.
すなわち，最大枚数になっている領域は必ずいずれかの交点を含む．
すべての交点を求め，そこから半径１以内の円の中心をカウントすれば良い．
サンプルが貧弱すぎてやばい．+1e-15してなかったらWAになる．
交点座標はcomplex型で楽させてもらった．

#include<iostream>
#include<vector>
#include<complex>
#include<cstdio>
#include<cmath>
using namespace std;
complex<double> I(0,1);
int main()
{
	int n;
	while( cin >> n , n )
	{
		vector<complex<double> > in;
		for( int i=0; i<n; ++i )
		{
			double x,y;
			scanf("%lf,%lf",&x,&y);
			in.push_back( complex<double>(x,y) );
		}
		
		vector<complex<double> > cp;
		for( int i=0; i<n-1; ++i )
		{
			for( int j=i+1; j<n; ++j )
			{
				if( norm( in[i]-in[j] ) <= 4.0 )
				{
					complex<double> a( (in[i]-in[j])*0.5 );
					complex<double> b( a*I );
					b /= abs(b);
					b *= sqrt(1-norm(a));
					cp.push_back( in[j]+a+b );
					cp.push_back( in[j]+a-b );
				}
			}
		}
		int ans = 1;
		for( int i=0; i<cp.size(); ++i )
		{
			int a = 0;
			for( int j=0; j<n; ++j )
			{
				if ( norm( cp[i]-in[j] ) <= 1.0 + 1e-15 )
				{
					a++;
				}
			}
			ans = max( ans , a );
		}
		cout << ans << endl;
	}
	return 0;
}