Problem:


シールの重なり

1 辺の長さが 10 の正方形の折り紙に半径 1 の円形のシールを n 枚貼ります。シールは重ねて貼ることができます。シールを貼る位置の座標を読み込んで、折り紙上でもっとも多くシールが重なっている場所(シールが１枚だけでも"重なっている"とする)でのシールの枚数を出力するプログラムを作成してください。

折り紙の左下を原点とした x, y 座標を与えます。この x, y を円の中心としてシールを貼ることとします。円の中心が折り紙の外に出ることはありません。また、同一座標に複数のシールが貼られることはありません。

Input

複数のデータセットが与えられます。各データセットは以下のような形式で与えられます。

n 
x1,y1
x2,y2
: 
xn,yn

１行目にシールの枚数 n (0 ≤ 100) が与えられます。続く n 行に、各シールの中心座標が与えられます。
xi, yi は i 枚目のシールの中心の x 座標と y 座標を表します。各値は小数点以下最大 6 桁までの数字を含む実数で与えられます。

n が 0 のとき、入力の最後とします。データセットの数は 50 を超えません。

Output

各データセットに対し、折り紙上で最も多くシールが重なっている場所でのシールの枚数（整数）を出力して下さい。

Sample Input

15
3.14979,8.51743 
2.39506,3.84915 
2.68432,5.39095 
5.61904,9.16332 
7.85653,4.75593 
2.84021,5.41511 
1.79500,8.59211 
7.55389,8.17604 
4.70665,4.66125 
1.63470,4.42538 
7.34959,4.61981 
5.09003,8.11122 
5.24373,1.30066 
0.13517,1.83659 
7.57313,1.58150 
0

Output for the Sample Input

4

Hint

入力例のようにシールを貼った図です。円はシール、数字は入力例の行数を表しています。
点(2.3,4.6)では、入力例の 2 行目、3 行目、6 行目、10 行目の 4 枚のシールが重なっています。

6 と 9 のおのおのの中心の距離は 2.01293 なので、シールは重なっていません。1 と 12 のおのおのの中心の距離は 1.98231 なので、シールは重なっています。

２つの円が接しているとき（おのおのの中心の距離が 2 のとき）は、重なっているものとします。　



Sample input:
15
3.14979,8.51743
2.39506,3.84915
2.68432,5.39095
5.61904,9.16332
7.85653,4.75593
2.84021,5.41511
1.79500,8.59211
7.55389,8.17604
4.70665,4.66125
1.63470,4.42538
7.34959,4.61981
5.09003,8.11122
5.24373,1.30066
0.13517,1.83659
7.57313,1.58150
0


Sample output:
4

Submission status: Runtime Error

Solution code:
#include <complex>
#include <iostream>
using namespace std;
complex<double> A[100],j=sqrt(-1),p;
double a,b,d;
int n;
int f(int m,int i1,int i2){
	int i,s1=2,s2=2;
	complex<double> p1=polar(1.0,b+d)+p,p2=polar(1.0,b-d)+p;
	for(i=0;i<n;i++){
		if(i==i1||i==i2)continue;
		if(abs(A[i]-p1)-1<1e-6)s1++;
		if(abs(A[i]-p2)-1<1e-6)s2++;
	}
	if(m<s1)m=s1;
	if(m<s2)m=s2;
	return m;
}
int main(){
	int m,i,i1;
	char c;
	while(cin>>n,n!=0){
		for(i=0;i<n;i++){
			cin>>a>>c>>b;
			A[i]=complex<double>(a,b);
		}
		m=1;
		for(i=0;i<n;i++){
			p=A[i];
			for(i1=i+1;i1<n;i1++){
				a=abs(A[i1]-p);
				b=arg(A[i1]-p);
				d=acos(a/2);
				if(a<=2)m=f(m,i,i1);
			}
		}
		cout<<m<<endl;
	}
}

Submission status: Runtime Error

Solution code:
#include <complex>
#include <iostream>
#include <vector>
using namespace std;
typedef complex<double> P;
P A[100],j=sqrt(-1);
double a,b,d;
int n;
int f(int m,P p,P p1){
	int i,s1=2,s2=2;
	P p3=polar(1.0,b+d)+p,p4=polar(1.0,b-d)+p,q;
	for(i=0;i<n;i++){
		q=A[i];
		if(q==p||q==p1)continue;
		if(abs(q-p3)-1<1e-6)s1++;
		if(abs(q-p4)-1<1e-6)s2++;
	}
	if(m<s1)m=s1;
	if(m<s2)m=s2;
	return m;
}
int main(){
	int m,i,i1;
	char c;
	while(cin>>n,n!=0){
		for(i=0;i<n;i++){
			cin>>a>>c>>b;A[i]=P(a,b);
		}
		m=1;
		for(i=0;i<n;i++){
			P p=A[i],q;
			for(i1=i+1;i1<n;i1++){
				q=A[i1];a=abs(q-p);b=arg(q-p);d=acos(a/2);
				if(a<=2)m=f(m,p,q);
			}
		}
		cout<<m<<endl;
	}
}

Submission status: Runtime Error

Solution code:
from math import sqrt
EPS = 10**(-8)
N = 100
def intersection(p, q, s, t):
    a = 2*(p-s)
    b = 2*(q-t)
    c = (p**2+q**2) - (s**2+t**2)
    A = a**2 + b**2
    Bx = p*b**2 + a*(c-q*b)
    Cx = (p**2+q**2-1)*b**2 - 2*b*c*q + c**2
    Dx = Bx**2-A*Cx
    #By = q*a**2 + b*(c-p*a)
    #Cy = (p**2+q**2-1)*a**2 - 2*a*c*p + c**2
    #Dy = By**2-A*Cy
    x0 = (-sqrt(Dx)+Bx)/A; y0 = (-x0*a + c)/b;
    x1 = (sqrt(Dx)+Bx)/A; y1 = (-x1*a + c)/b;
    return [x0, y0], [x1, y1]
def dist(p, q, s, t):
    return (p-s)**2 + (q-t)**2
while True:
    n = input()
    if n==0:
        break
    x,y = [0.0]*N,[0.0]*N
    ans = 0
    for i in xrange(n):
        x[i], y[i] = map(float, raw_input().split(','))
    for i in xrange(n):
        for j in xrange(i+1, n):
            rr = dist(x[i], y[i], x[j], y[j])
            if rr<4.00+EPS:
                if rr<EPS:
                    cnt = 2
                    for k in xrange(n):
                        if k==i or k==j:
                            continue
                        if dist(x[i], y[i], x[k], y[k])<1.00+EPS:
                            cnt += 1
                    ans = max(ans, cnt)
                else:
                    xi = [0.0]*2; yi = [0.0]*2
                    [xi[0], yi[0]], [xi[1], yi[1]] = intersection(x[i], y[i], x[j], y[j])
                    for t in xrange(2):
                        #print xi[t],yi[t], "(", i, j,")"
                        cnt = 2
                        for k in xrange(n):
                            if k==i or k==j:
                                continue
                            rri = dist(xi[t], yi[t], x[k], y[k])
                            if rri<1.00+EPS:
                                cnt += 1
                                #print k, rri
                        #print ">>",cnt
                        ans = max(ans, cnt)
    print ans

Submission status: Runtime Error

Solution code:
from math import sqrt
EPS = 10**(-8)
N = 100
def intersection(p, q, s, t):
    a = 2*(p-s)
    b = 2*(q-t)
    c = (p**2+q**2) - (s**2+t**2)
    A = a**2 + b**2
    Bx = p*b**2 + a*(c-q*b)
    Cx = (p**2+q**2-1)*b**2 - 2*b*c*q + c**2
    Dx = Bx**2-A*Cx
    #By = q*a**2 + b*(c-p*a)
    #Cy = (p**2+q**2-1)*a**2 - 2*a*c*p + c**2
    #Dy = By**2-A*Cy
    x0 = (-sqrt(Dx)+Bx)/A; y0 = (-x0*a + c)/b;
    x1 = (sqrt(Dx)+Bx)/A; y1 = (-x1*a + c)/b;
    return x0, y0, x1, y1
def dist(p, q, s, t):
    return (p-s)**2 + (q-t)**2
x,y = [0.0]*N,[0.0]*N
xi = [0.0]*2; yi = [0.0]*2
while True:
    n = input()
    if n==0:
        break
    ans = 1
    for i in xrange(n):
        x[i], y[i] = map(float, raw_input().split(','))
    for i in xrange(n):
        for j in xrange(i+1, n):
            rr = dist(x[i], y[i], x[j], y[j])
            if rr<4.00+EPS:
                if rr<EPS:
                    cnt = 2
                    for k in xrange(n):
                        if k==i or k==j:
                            continue
                        if dist(x[i], y[i], x[k], y[k])<1.00+EPS:
                            cnt += 1
                    ans = max(ans, cnt)
                else:
                    xi[0], yi[0], xi[1], yi[1] = intersection(x[i], y[i], x[j], y[j])
                    for t in xrange(2):
                        #print xi[t],yi[t], "(", i, j,")"
                        cnt = 2
                        for k in xrange(n):
                            if k==i or k==j:
                                continue
                            rri = dist(xi[t], yi[t], x[k], y[k])
                            if rri<1.00+EPS:
                                cnt += 1
                                #print k, rri
                        #print ">>",cnt
                        ans = max(ans, cnt)
    print ans

Submission status: Runtime Error

Solution code:
from math import sqrt
EPS = 10**(-8)
N = 100
def intersection(p, q, s, t):
    a = 2*(p-s)
    b = 2*(q-t)
    c = (p**2+q**2) - (s**2+t**2)
    A = a**2 + b**2
    x0, y0, x1, y1 = [0.0]*4
    if A<EPS:
        return p, q, s, t
    Bx = p*b**2 + a*(c-q*b)
    Cx = (p**2+q**2-1)*b**2 - 2*b*c*q + c**2
    Dx = Bx**2-A*Cx
    By = q*a**2 + b*(c-p*a)
    Cy = (p**2+q**2-1)*a**2 - 2*a*c*p + c**2
    Dy = By**2-A*Cy
    if b>EPS:
        x0 = (-sqrt(Dx)+Bx)/A; y0 = (-x0*a + c)/b;
        x1 = (sqrt(Dx)+Bx)/A; y1 = (-x1*a + c)/b;
    else:
        x0 = (-y0*b + c)/a; y0 = (-sqrt(Dy)+By)/A;
        x1 = (-y1*b + c)/a; y1 = (sqrt(Dy)+By)/A;
    return x0, y0, x1, y1
def dist(p, q, s, t):
    return (p-s)**2 + (q-t)**2
x,y = [0.0]*N,[0.0]*N
xi = [0.0]*2; yi = [0.0]*2
while True:
    n = input()
    if n==0:
        break
    ans = 1
    for i in xrange(n):
        x[i], y[i] = map(float, raw_input().split(','))
    for i in xrange(n):
        for j in xrange(i+1, n):
            rr = dist(x[i], y[i], x[j], y[j])
            if rr<4.00+EPS:
                if rr<EPS:
                    cnt = 2
                    for k in xrange(n):
                        if k==i or k==j:
                            continue
                        if dist(x[i], y[i], x[k], y[k])<1.00+EPS:
                            cnt += 1
                    ans = max(ans, cnt)
                else:
                    xi[0], yi[0], xi[1], yi[1] = intersection(x[i], y[i], x[j], y[j])
                    for t in xrange(2):
                        #print xi[t],yi[t], "(", i, j,")"
                        cnt = 2
                        for k in xrange(n):
                            if k==i or k==j:
                                continue
                            rri = dist(xi[t], yi[t], x[k], y[k])
                            if rri<1.00+EPS:
                                cnt += 1
                                #print k, rri
                        #print ">>",cnt
                        ans = max(ans, cnt)
    print ans