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: Wrong Answer

Solution code:
import math,cmath
def f(m):
  c=math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=0,0
  for k in N:
    if k==i or k==j:continue
    if abs(p1-X[k])<=1.01:s1+=1
    if abs(p2-X[k])<=1.01:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[complex(x,y)]
  m=0
  for i in N:
    p0=X[i]
    for j in N:
      if i==j:continue
      a,b=cmath.polar(p0-X[j])
      b*=1j
      if a<=2:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
def f(m):
  c=math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=0,0
  for k in N:
    if k==i or k==j:continue
    if abs(p1-X[k])<=1+1e-5:s1+=1
    if abs(p2-X[k])<=1+1e-5:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[complex(x,y)]
  m=0
  for i in N:
    p0=X[i]
    for j in N:
      if i==j:continue
      a,b=cmath.polar(p0-X[j])
      b*=1j
      if a<=2:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
EPS=1e-6
def f(m):
  c=math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=0,0
  for k in N:
    if k==i or k==j:continue
    if abs(p1-X[k])<1+EPS:s1+=1
    if abs(p2-X[k])<1+EPS:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[complex(x,y)]
  m=0
  for i in N:
    p0=X[i]
    for j in N:
      if i==j:continue
      a,b=cmath.polar(p0-X[j])
      b*=1j
      if a<=2:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-6
def f(m):
  c=1j*math.acos(a/2)
  def g(c):
    return cmath.exp(b+c)+p0
  p1,p2=g(c),g(-c)
  s1,s2=0,0
  for k in N:
    if k==i or k==j:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=0
  for i in N:
    p0=X[i]
    for j in N:
      if i==j:continue
      a,b=cmath.polar(X[j]-p0)
      b*=1j
      if a<=2:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-6
def f(m):
  c=1j*math.acos(a/2)
  def g(c):
    return cmath.exp(b+c)+p0
  p1,p2=g(c),g(-c)
  s1,s2=0,0
  for k in N:
    if k==i or k==j:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=0
  for i in N:
    p0=X[i]
    for j in N:
      if i==j:continue
      a,b=cmath.polar(X[j]-p0)
      b*=1j
      if a<2+e:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-8
def f(m):
  c=1j*math.acos(a/2)
  def g(c):
    return cmath.exp(b+c)+p0
  p1,p2=g(c),g(-c)
  s1,s2=0,0
  for k in N:
    if k==i or k==j:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=0
  for i in N:
    p0=X[i]
    for j in N:
      if i==j:continue
      a,b=cmath.polar(X[j]-p0)
      b*=1j
      if a<2+e:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-5
def f(m):
  c=1j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=0,0
  for k in N:
    if k==i or k==i1:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=0
  for i in N:
    p0=X[i]
    for i1 in N:
      if i==i1:continue
      p=X[i1]-p0
      a,b=cmath.polar(p)
      if p.real<0:b+=cmath.pi
      b*=1j
      if a<2+e:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-8
j=1j
def f(m):
  c=j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=0,0
  for k in N:
    if k==i or k==i1:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+j*y]
  m=0
  for i in N:
    p0=X[i]
    for i1 in N:
      if i==i1:continue
      p=X[i1]-p0
      a,b=cmath.polar(p)
      b*=j
      if a<=2:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-5
j=1j
def f(m):
  c=j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=0,0
  for k in N:
    if k==i or k==i1:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+j*y]
  m=0
  for i in N:
    p0=X[i]
    for i1 in N:
      if i==i1:continue
      p=X[i1]-p0
      a,b=cmath.polar(p)
      b*=j
      if a<=2:m=f(m)
  print m+2

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-5
j=1j
def f(m):
  c=j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=2,2
  for k in N:
    if k==i or k==i1:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+j*y]
  m=0
  for i in N:
    p0=X[i]
    for i1 in N:
      if i==i1:continue
      p=X[i1]-p0
      a,b=cmath.polar(p)
      b*=j
      if a<=2:m=f(m)
  print m

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-6
j=1j
def f(m):
  c=j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=2,2
  for k in N:
    if k==i or k==i1:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+j*y]
  m=0
  for i in N:
    p0=X[i]
    for i1 in N:
      if i==i1:continue
      p=X[i1]-p0
      a,b=cmath.polar(p)
      b*=j
      if a<=2:m=f(m)
  print m

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-7
j=1j
def f(m):
  c=j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=2,2
  for k in N:
    if k==i or k==i1:continue
    if abs(p1-X[k])<1+e:s1+=1
    if abs(p2-X[k])<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+j*y]
  m=0
  for i in N:
    p0=X[i]
    for i1 in N:
      if i==i1:continue
      p=X[i1]-p0
      a,b=cmath.polar(p)
      b*=j
      if a<=2:m=f(m)
  print m

Submission status: Wrong Answer

Solution code:
import math,cmath
e=1e-6
def f(m):
  c=1j*math.acos(a/2)
  p1=cmath.exp(b+c)+p
  p2=cmath.exp(b-c)+p
  s1,s2=2,2
  for p3 in X:
    if p!=p3!=p0:continue
    if abs(p3-p1)<1+e:s1+=1
    if abs(p3-p2)<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=1
  for i in N:
    p=X[i]
    for p0 in X[i+1:]:
      a,b=cmath.polar(p0-p)
      b*=1j
      if a<=2:m=f(m)
  print m

Submission status: Time Limit Exceeded

Solution code:
from math import sin,cos,pi
x=[0]*100;y=[0]*100
h=1000
while 1:
    n=int(input())
    if n==0:break
    a=0
    for i in range(n):x[i],y[i]=map(float,input().split(','))
    for i in range(n):
        for j in range(h):
            cx=x[i]+cos(2*pi*j/h)
            cy=y[i]+sin(2*pi*j/h)
            c=0
            for k in range(n):
                if (cx-x[k])*(cx-x[k])+(cy-y[k])*(cy-y[k])<1.0+1e-7:c+=1
            a=max(a,c)
    print(a)

Submission status: Memory Limit Exceeded

Solution code:
def dist2(pt1,pt2):
    return ((pt1[0]-pt2[0])**2+(pt1[1]-pt2[1])**2)<=4


while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        plist=[]
        for i in range(n):
            plist.append([float(x) for x in raw_input().split(',')])
        graphlist=[]
        for i in range(n):
            gilist=[]
            for j in range(n):
                if i!=j and dist2(plist[i],plist[j]):
                    gilist.append(j)
            graphlist.append(gilist)
        maxcreek=[[x] for x in range(n)]
        while(1):
            newmaxcreek=[]
            for creek in maxcreek:
                pt=creek[0]
                for p in [x for x in graphlist[pt] if x not in creek]:
                    for pts in creek[1:]:
                        if p not in graphlist[pts]:
                            break
                    else:
                        newmaxcreek.append(creek+[p])
            if len(newmaxcreek)==0:
                print max(map(len,maxcreek))
                break
            else:
                maxcreek=newmaxcreek[:]

Submission status: Accepted

Solution code:
import math
while True:
    n = input()
    if (n == 0):
        break
    d = []
    EPS = 10 ** (-6)

    for i in range(n):
        a = map(float, raw_input().split(","))
        x = a[0]
        y = a[1]
        d.append([y,x])
    ans = 1
    for Y in range(0, 100):
        for X in range(0, 100):
            y1 = 1.0 * Y / 10
            x1 = 1.0 * X / 10
            sheet = 0
            for i in range(n):
                dist = (d[i][0] - y1) ** 2 + (d[i][1] - x1) ** 2
                if (dist <= 1.0):
                    sheet += 1
            ans = max(ans, sheet)
    print ans

Submission status: Accepted

Solution code:
import math,cmath

def f(m):
    c=1j*math.acos(a/2)
    r=cmath.exp(b+c)+p
    s=cmath.exp(b-c)+p
    u=v=2
    for t in A:
        if t in [p,q]:
            continue
        if abs(t-r)-1<1e-6:
            u+=1
        if abs(t-s)-1<1e-6:
            v+=1
    return max(m,u,v)

while 1:
    n=int(raw_input())
    if n==0:
        break
    N=range(n)
    A=[]
    for i in N:
        #x,y=map(float,int(raw_input()))
        x,y=map(float,input())
        A+=[x+1j*y]
    m=1
    for i in N:
        p=A[i]
        for q in A[i+1:]:
            a,b=cmath.polar(q-p)
            b*=1j
            if a<=2:
                m=f(m)
    print m

Submission status: Accepted

Solution code:
import itertools
x=[0.]*100;y=[0.]*100
while 1:
    n=int(input())
    if n==0:break
    a=0
    for i in range(n):x[i],y[i]=map(float,input().split(','))
    for i,j in itertools.product(range(100),range(100)):
            c=0
            for k in range(n):
                if pow(x[k]-(i/10),2)+pow(y[k]-(j/10),2)<=1.01:c+=1
            if c>a:a=c
    print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

for s in sys.stdin:

    n = int(s)
    if n == 0:
        break
    P = []

    for i in range(n):
        x, y = map(float, input().split(','))
        P.append(complex(x, y))

    def get_intersections(p0, p1):
        """
        :type p0: complex
        :type p1: complex
        :return:
        """
        dist = abs(p0 - p1)

        if dist > 2:
            return []
        elif dist == 2:
            return [(p0 + p1) / 2]
        else:
            m = (p0 + p1) / 2
            v = m - p0
            w = complex(v.imag, -v.real)
            n = w / abs(w)
            d = abs(v)
            l = math.sqrt(1 - d ** 2)

            inter0 = m + l * n
            inter1 = m - l * n
            return [inter0, inter1]


    intersections = []
    for i in range(n):
        for j in range(i+1, n):
            intersections += get_intersections(P[i], P[j])

    counts = []

    # each intersection, it is in how many circles?
    for intersection in intersections:
        cnt = 0
        for p in P:
            if abs(intersection - p) <= 1.01:
                cnt += 1
        counts.append(cnt)

    if counts:
        print(max(counts))
    else:
        print(1)

Submission status: Accepted

Solution code:
import sys
import os
import math
 
for s in sys.stdin:
 
    n = int(s)
    if n == 0:
        break
    P = []
 
    for i in range(n):
        x, y = map(float, input().split(','))
        P.append(complex(x, y))
 
    def get_intersections(p0, p1):
        """
        :type p0: complex
        :type p1: complex
        :return:
        """
        dist = abs(p0 - p1)
 
        if dist > 2:
            return []
        elif dist == 2:
            return [(p0 + p1) / 2]
        else:
            m = (p0 + p1) / 2
            v = m - p0
            w = complex(v.imag, -v.real)
            n = w / abs(w)
            d = abs(v)
            l = math.sqrt(1 - d ** 2)
 
            inter0 = m + l * n
            inter1 = m - l * n
            return [inter0, inter1]
 
 
    intersections = []
    for i in range(n):
        for j in range(i+1, n):
            intersections += get_intersections(P[i], P[j])
 
    counts = []
 
    # each intersection, it is in how many circles?
    for intersection in intersections:
        cnt = 0
        for p in P:
            if abs(intersection - p) <= 1.01:
                cnt += 1
        counts.append(cnt)
 
    if counts:
        print(max(counts))
    else:
        print(1)

Submission status: Accepted

Solution code:
import math

def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def intersection(o1,o2):
    if dist(o1,o2) > 2:
        p1, p2 =  [None, None], [None, None]
    elif dist(o1,o2) == 2:
        p1, p2 =  [(o1[0] + o2[0])/2, (o1[1] + o2[1])/2], [None, None]
    else:
        m = [(o1[0] + o2[0])/2, (o1[1] + o2[1])/2]
        v = [m[0] - o1[0], m[1] - o1[1]]
        v_abs = dist(v,[0,0])
        w = [v[1], -v[0]]
        w_abs = dist(w,[0,0])
        n = [w[0]/w_abs, w[1]/w_abs]
        l = math.sqrt(1 - v_abs**2)
        p1 = [m[0] + l*n[0], m[1] + l*n[1]]
        p2 = [m[0] - l*n[0], m[1] - l*n[1]]
    return p1, p2
err = 1.0e-6
while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1[0] and dist(p1, p[k]) <= 1 + err:
                    cnt1 += 1
                if p2[0] and dist(p2, p[k]) <= 1 + err:
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Accepted

Solution code:
import itertools
x=[0.]*100;y=[0.]*100
for e in iter(input,'0'):
    a=0
    n=int(e)
    for i in range(n):x[i],y[i]=map(float,input().split(','))
    for i,j in itertools.product(range(100),range(100)):
            c=0
            for k in range(n):
                if pow(x[k]-(i/10),2)+pow(y[k]-(j/10),2)<=1.01:c+=1
            if c>a:a=c
    print(a)

Submission status: Accepted

Solution code:
def get_intersections(p0, p1):
    dist = abs(p0 - p1)

    if dist > 2:
        return []
    elif dist == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        n = w / abs(w)
        d = abs(v)
        l = (1 - d ** 2)**.5

        inter0 = m + l * n
        inter1 = m - l * n
        return [inter0, inter1]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float,input().split(',')))for _ in[0]*n]
    intersections = []
    for i in range(n):
        for j in range(i+1,n):
            intersections += get_intersections(P[i], P[j])
    c = 1
    for intersection in intersections:
        cnt = 0
        for p in P:
            if abs(intersection - p) <= 1.01:
                cnt += 1
        c=max(c,cnt)
    print(c)

Submission status: Accepted

Solution code:
def x(p0, p1):
    d = abs(p0 - p1)
    if d > 2:
        return []
    elif d == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        l = abs(w)
        h = (1 - l ** 2) ** .5 * w / l
        return [m + h, m - h]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float, input().split(','))) for _ in [0] * n]
    Q = []
    for i in range(n):
        for j in range(i + 1, n):
            Q += x(P[i], P[j])
    print(max(sum(1.01 >= abs(q - p) for p in P) for q in Q) if Q else 1)

Submission status: Accepted

Solution code:
def x(p0, p1):
    d = abs(p0 - p1)
    if d > 2:
        return []
    elif d == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        l = abs(w)
        h = (1 - l ** 2) ** .5 * w / l
        return [m + h, m - h]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float, input().split(','))) for _ in [0] * n]
    Q = []
    for i in range(n):
        for j in range(i + 1, n):
            Q += x(P[i], P[j])
    print(max([sum(1.01 >= abs(q - p) for p in P) for q in Q] + [1]))

Submission status: Accepted

Solution code:
def x(p0, p1):
    d = abs(p0 - p1)
    if d > 2:
        return []
    elif d == 2:
        return [(p0 + p1) / 2]
    else:
        m = (p0 + p1) / 2
        v = m - p0
        w = complex(v.imag, -v.real)
        l = abs(w)
        h = (1 - l ** 2) ** .5 * w / l
        return [m + h, m - h]

for e in iter(input, '0'):
    n = int(e)
    P = [complex(*map(float, input().split(','))) for _ in [0] * n]
    Q = []
    for i in range(n):
        for j in range(i + 1, n):
            Q += x(P[i], P[j])
    print(max([sum(1.02 >= abs(q - p) for p in P) for q in Q] + [1]))

Submission status: Accepted

Solution code:
# AOJ 0090: Overlaps of Seals
# Python3 2018.6.28 bal4u

EPS = 1.0e-8

def crossPoint(p1, p2):
	A = (p1.real-p2.real)/2
	B = (p1.imag-p2.imag)/2
	d = (A*A + B*B)**0.5
	if d*d > 1.0 + EPS: return;
	h = (1 - d*d)**0.5;
	k, X, Y = h/d, (p1.real+p2.real)/2, (p1.imag+p2.imag)/2;
	cross.append(complex(X+k*B, Y-k*A))
	cross.append(complex(X-k*B, Y+k*A))

while True:
	n = int(input())
	if n == 0: break
	circle = [0] * n
	for i in range(n):
		x, y = map(float, input().split(','))
		circle[i] = complex(x, y)
	cross = []
	for i in range(n):
		for j in range(i+1, n):	crossPoint(circle[i], circle[j]);
	ans = 0
	for i in cross:
		f = 0
		for j in circle:
			dx = j.real - i.real
			dy = j.imag - i.imag
			d = dx*dx + dy*dy
			if abs(d-1.0) <= EPS or d <= 1.0: f += 1
		if f > ans: ans = f
	print(1 if ans == 0 else ans)

Submission status: Accepted

Solution code:
import itertools,math
def isOverlapped(x1,y1,x2,y2,r1,r2):        
    return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))**0.5<=r1+r2+0.000009
while True:
    n=input()
    if n==0:
        break
    li=[]
    for i in xrange(n):
        li.append(map(float,raw_input().split(",")))
    ma=1
    for i,j in itertools.combinations(xrange(n),2):
        if isOverlapped(li[i][0],li[i][1],li[j][0],li[j][1],1,1):
            L=((li[i][0]-li[j][0])**2+(li[i][1]-li[j][1])**2)**0.5
            t=math.atan2(li[j][1]-li[i][1],li[j][0]-li[i][0])
            al=math.acos(L/2)
            node=[[li[i][0]+math.cos(t+al),li[i][1]+math.sin(t+al)],
                  [li[i][0]+math.cos(t-al),li[i][1]+math.sin(t-al)]]
            for p in xrange(2):
                c=0
                for q in xrange(n):
                    if isOverlapped(node[p][0],node[p][1],li[q][0],li[q][1],0,1):
                        c+=1
                ma=max(c,ma)
    print ma

Submission status: Accepted

Solution code:
import itertools,math
def isOverlapped(x1,y1,x2,y2,r1,r2):        
    return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))**0.5<=r1+r2+0.000009
while True:
    n=input()
    if n==0:
        break
    li=[]
    for i in xrange(n):
        li.append(map(float,raw_input().split(",")))
    ma=1
    for i,j in itertools.combinations(xrange(n),2):
        x1,y1,x2,y2=li[i][0],li[i][1],li[j][0],li[j][1]
        if isOverlapped(x1,y1,x2,y2,1,1):
            L=((x1-x2)**2+(y1-y2)**2)**0.5
            t=math.atan2(y2-y1,x2-x1)
            al=math.acos(L/2)
            node=[[x1+math.cos(t+al),y1+math.sin(t+al)],
                  [x1+math.cos(t-al),y1+math.sin(t-al)]]
            for p in xrange(2):
                c=0
                for q in xrange(n):
                    if isOverlapped(node[p][0],node[p][1],li[q][0],li[q][1],0,1):
                        c+=1
                ma=max(c,ma)
    print ma

Submission status: Accepted

Solution code:
from __future__ import division
import math

def cross(p1,p2):
    a,b,c,d=p1[0],p1[1],p2[0],p2[1]
    t=pow(a,2)+pow(c,2)+pow(d,2)-pow(b,2)-2*a*c
    alpha=4*(pow(b-d,2)+pow(c-a,2))
    beta=4*(t*(b-d)-2*b*pow(c-a,2))
    gamma=pow(t,2)+4*pow(b,2)*pow(c-a,2)-4*pow(c-a,2)
    judge=pow(beta,2)-4*alpha*gamma
    EPS=1e-5
    if c==a:
        y=(pow(a,2)+pow(b,2)-pow(c,2)-pow(d,2))/(2*(b-d))
        bd=pow(b-d,2)
        a1=4*bd
        b1=-8*a*bd
        c1=4*a*a*bd+pow(a*a-b*b-c*c-d*d+2*b*d,2)-4*bd
        inroot=pow(b1,2)-4*a1*c1
        if inroot<0:
            return None
        x1=(-b1+math.sqrt(inroot))/(2*a1)
        x2=(-b1-math.sqrt(inroot))/(2*a1)
        return ((x1,y),(x2,y))

    if judge>EPS:
        y1=(-beta+math.sqrt(judge))/(2*alpha)
        y2=(-beta-math.sqrt(judge))/(2*alpha)
        x1=(2*(b-d)*y1+pow(c,2)+pow(d,2)-pow(a,2)-pow(b,2))/(2*(c-a))
        x2=(2*(b-d)*y2+pow(c,2)+pow(d,2)-pow(a,2)-pow(b,2))/(2*(c-a))
        return ((x1,y1),(x2,y2))
    elif -EPS<=judge<=EPS:
        y=-beta/(2*alpha)
        x=(2*(b-d)*y+pow(c,2)+pow(d,2)-pow(a,2)-pow(b,2))/(2*(c-a))
        return ((x,y),)
    else:
        return None

def maxNum(P,L):
    ans=1
    for x,y in P:
        cnt=0
        for px,py in L:
            d=math.sqrt(pow(px-x,2)+pow(py-y,2))
            if d<=1:
                cnt+=1
        ans=max(ans,cnt)
    return ans

while True:
    n=input()
    if n==0:break
    L=[map(float,raw_input().split(",")) for i in range(n)]
    P=[]
    for i in range(n-1):
        for j in range(i+1,n):
            points=cross(L[i],L[j])
            if points:
                P.extend(points)
    print maxNum(P,L)

Submission status: Accepted

Solution code:
def isOver(array,x,y):
	return True if (array[0]-x)**2+(array[1]-y)**2 <= 1.01 else False
	
while True:
    mx = 0
    n = int(raw_input())
    if n == 0: break
    seals = [map(float, raw_input().split(",")) for i in range(n)]
    x = 0
    while x < 10.0:
    	y = 0.0
    	while y < 10.0:
    		num = 0
    		for seal in seals:
    			if isOver(seal,x,y):
    				num += 1
    		mx = max(mx,num)
    		y += 0.1
        x += 0.1
    print mx

Submission status: Accepted

Solution code:
import math,cmath
e=1e-6
j=1j
def f(m):
  c=j*math.acos(a/2)
  p1=cmath.exp(b+c)+p0
  p2=cmath.exp(b-c)+p0
  s1,s2=2,2
  for k in N:
    if k==i or k==i1:continue
    if abs(X[k]-p1)<1+e:s1+=1
    if abs(X[k]-p2)<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+j*y]
  m=1
  for i in N:
    p0=X[i]
    for i1 in range(i+1,n):
      p=X[i1]-p0
      a,b=cmath.polar(p)
      b*=j
      if a<=2:m=f(m)
  print m

Submission status: Accepted

Solution code:
import math,cmath
e=1e-6
def f(m):
  c=1j*math.acos(a/2)
  p1=cmath.exp(b+c)+p
  p2=cmath.exp(b-c)+p
  s1,s2=2,2
  for k in N:
    if k in[i,i1]:continue
    if abs(X[k]-p1)<1+e:s1+=1
    if abs(X[k]-p2)<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=1
  for i in N:
    p=X[i]
    for i1 in range(i+1,n):
      a,b=cmath.polar(X[i1]-p)
      b*=1j
      if a<=2:m=f(m)
  print m

Submission status: Accepted

Solution code:
import math,cmath
e=1e-6
def f(m):
  c=1j*math.acos(a/2)
  p1=cmath.exp(b+c)+p
  p2=cmath.exp(b-c)+p
  s1,s2=2,2
  for p3 in X:
    if p3 in[p,p0]:continue
    if abs(p3-p1)<1+e:s1+=1
    if abs(p3-p2)<1+e:s2+=1
  return max(m,s1,s2)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  X=[]
  for i in N:
    x,y=map(float,input())
    X+=[x+1j*y]
  m=1
  for i in N:
    p=X[i]
    for p0 in X[i+1:]:
      a,b=cmath.polar(p0-p)
      b*=1j
      if a<=2:m=f(m)
  print m

Submission status: Accepted

Solution code:
import math,cmath
def f(m):
  c=1j*math.acos(a/2)
  r=cmath.exp(b+c)+p
  s=cmath.exp(b-c)+p
  u,v=2,2
  for t in A:
    if t in[p,q]:continue
    if abs(t-r)-1<1e-6:u+=1
    if abs(t-s)-1<1e-6:v+=1
  return max(m,u,v)

while 1:
  n=input()
  if n==0:break
  N=range(n)
  A=[]
  for i in N:
    x,y=map(float,input())
    A+=[x+1j*y]
  m=1
  for i in N:
    p=A[i]
    for q in A[i+1:]:
      a,b=cmath.polar(q-p)
      b*=1j
      if a<=2:m=f(m)
  print m

Submission status: Accepted

Solution code:
import math
while 1:
    N = int(input())
    if N == 0:
        break
 
    PS = []
    for i in range(N):
        x, y = map(float, input().split(','))
        PS.append((int(x * 100000), int(y * 100000)))
 
    D2 = 100000**2
    ans = 0
    for i in range(101):
        py = i * 10000
        for j in range(101):
            px = j * 10000
            cnt = 0
            for x, y in PS:
                if (px - x) ** 2 + (py - y) ** 2 <= D2:
                    cnt += 1
            ans = max(ans, cnt)
    print(ans)

Submission status: Accepted

Solution code:
import math
while 1:
    N = int(input())
    if N == 0:
        break

    PS = []
    for i in range(N):
        x, y = map(float, input().split(','))
        PS.append((int(x * 100000), int(y * 100000)))

    D2 = 100000**2
    ans = 0
    for i in range(101):
        py = i * 10000
        for j in range(101):
            px = j * 10000
            cnt = 0
            for x, y in PS:
                if (px - x) ** 2 + (py - y) ** 2 <= D2:
                    cnt += 1
            ans = max(ans, cnt)
    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

for s in sys.stdin:

    n = int(s)
    if n == 0:
        break
    P = []

    for i in range(n):
        x, y = map(float, input().split(','))
        P.append(complex(x, y))

    def get_intersections(p0, p1):
        """
        :type p0: complex
        :type p1: complex
        :return:
        """
        dist = abs(p0 - p1)

        if dist > 2:
            return []
        elif dist == 2:
            return [(p0 + p1) / 2]
        else:
            m = (p0 + p1) / 2
            v = m - p0
            w = complex(v.imag, -v.real)
            n = w / abs(w)
            d = abs(v)
            l = math.sqrt(1 - d ** 2)

            inter0 = m + l * n
            inter1 = m - l * n
            return [inter0, inter1]


    intersections = []
    for i in range(n):
        for j in range(i+1, n):
            intersections += get_intersections(P[i], P[j])

    counts = []

    # each intersection, it is in how many circles?
    for intersection in intersections:
        cnt = 0
        for p in P:
            if abs(intersection - p) <= 1:
                cnt += 1
        counts.append(cnt)

    print(max(counts))

Submission status: Runtime Error

Solution code:
import math

def overlap(p1, p2, d):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 <= d

def intersection(o1,o2):
    a  = 2*(o2[0] - o1[0])
    b  = 2*(o2[1] - o1[1])
    c  = (o1[0] - o2[0])*(o1[0] + o2[0]) + (o1[1] - o2[1])*(o1[1] + o2[1])
    
    a2 = a**2 + b**2
    b2 = a*c + a*b*o1[1] - b**2*o1[0]
    c2 = b**2*(o1[0]**2 + o1[1]**2 - 1) + c**2 + 2*b*c*o1[1]
    x1 = (-b2 + math.sqrt(b2**2 - a2*c2))/a2
    x2 = (-b2 - math.sqrt(b2**2 - a2*c2))/a2
    if b == 0:
        y1 = (o1[1] + o2[1])/2
        y2 = (o1[1] + o2[1])/2
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    if b2**2 - a2*c2 < 10e-6:
        return [x1, y1], [None, None]
    else:
        return [x1, y1], [x2, y2]

while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 4):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2[0] != None and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Runtime Error

Solution code:
import math

def overlap(p1, p2, d):
    return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 <= d

def intersection(o1,o2):
    a  = 2*(o2[0] - o1[0])
    b  = 2*(o2[1] - o1[1])
    c  = (o1[0] - o2[0])*(o1[0] + o2[0]) + (o1[1] - o2[1])*(o1[1] + o2[1])
    
    a2 = a**2 + b**2
    b2 = a*c + a*b*o1[1] - b**2*o1[0]
    c2 = b**2*(o1[0]**2 + o1[1]**2 - 1) + c**2 + 2*b*c*o1[1]
    x1 = (-b2 + math.sqrt(b2**2 - a2*c2))/a2
    x2 = (-b2 - math.sqrt(b2**2 - a2*c2))/a2
    if b == 0:
        y1 = (o1[1] + o2[1])/2
        y2 = (o1[1] + o2[1])/2
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    if b2**2 - a2*c2 < 10e-6:
        return [x1, y1], [None, None]
    else:
        return [x1, y1], [x2, y2]

while True:
    n = int(input())
    if n == 0:
        break
    p = []
    for i in range(n):
        p.append(list(map(float, input().split(","))))
    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 4):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2[0] != None and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)