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:
# -*- 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)

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

Submission status: Wrong Answer

Solution code:
import math

def overlap(p, o):
    return (p[0] - o[0])**2 + (p[1] - o[1])**2 <= 4

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 = 2*(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]
    if b2**2 - a2*c2 < 0:
        return [None, None], [None, None]
    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
    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):
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            if p1[0] == None:
                continue
            for k in range(n):
                if overlap(p1, p[k]):
                    cnt1 += 1
                if overlap(p2, p[k]):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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())
    sys.exit()
    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
            elif overlap(p[i], p[j], 10e-6):
                continue
            p1, p2 = intersection(p[i], p[j])
            print(p1,p2)
            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
            print(ans, cnt1, cnt2)
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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
    sys.exit()
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 4):
                continue
            elif overlap(p[i], p[j], 10e-6):
                continue
            p1, p2 = intersection(p[i], p[j])
            print(p1,p2)
            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
            print(ans, cnt1, cnt2)
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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
            elif overlap(p[i], p[j], 10e-6):
                continue
            sys.exit()
            p1, p2 = intersection(p[i], p[j])
            print(p1,p2)
            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
            print(ans, cnt1, cnt2)
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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
            elif overlap(p[i], p[j], 10e-6):
                continue
            p1, p2 = intersection(p[i], p[j])
            sys.exit()
            print(p1,p2)
            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
            print(ans, cnt1, cnt2)
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys

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
            elif overlap(p[i], p[j], 10e-6):
                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])
    sys.exit()
    print(ans)

Submission status: Wrong Answer

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 < 10e-6:
        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
            elif overlap(p[i], p[j], 10e-6):
                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)
    break

Submission status: Wrong Answer

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(abs(b2**2 - a2*c2)))/a2
    x2 = (-b2 - math.sqrt(abs(b2**2 - a2*c2)))/a2
    if abs(b) < 10e-6:
        y1 = (o1[1] + o2[1])/2
        y2 = (o1[1] + o2[1])/2
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    if abs(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
            elif overlap(p[i], p[j], 10e-6):
                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: Wrong Answer

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(abs(b2**2 - a2*c2)))/a2
    x2 = (-b2 - math.sqrt(abs(b2**2 - a2*c2)))/a2
    if abs(b) < 10e-8:
        y1 = (o1[1] + o2[1])/2
        y2 = (o1[1] + o2[1])/2
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    if abs(b2**2 - a2*c2) < 10e-8:
        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
            elif overlap(p[i], p[j], 10e-8):
                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: Wrong Answer

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(abs(b2**2 - a2*c2)))/a2
    x2 = (-b2 - math.sqrt(abs(b2**2 - a2*c2)))/a2
    if abs(b) < 10e-8:
        y1 = (o1[1] + o2[1])/2
        y2 = (o1[1] + o2[1])/2
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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
            elif overlap(p[i], p[j], 10e-8):
                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: Wrong Answer

Solution code:
import math

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

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(abs(b2**2 - a2*c2)))/a2
    x2 = (-b2 - math.sqrt(abs(b2**2 - a2*c2)))/a2
    if abs(b) == 0:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                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 overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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(abs(b2**2 - a2*c2)))/a2
    x2 = (-b2 - math.sqrt(abs(b2**2 - a2*c2)))/a2
    if abs(b) == 0:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                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 overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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 abs(b) == 0:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                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 overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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 abs(b) == 0:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                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 overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

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]
    judge = b2**2 - a2*c2
    if judge < 0:
        return None, None
    elif abs(judge) < 1.0e-6:
        x = -b2/a2
        if abs(b) < 1.0e-6:
            y = o1[1] + math.sqrt(1 - (x - o1[0])**2)
        else:
            y = -(a*x + c)/b
        return [x,y], None
    else:
        x1 = (-b2 + math.sqrt(judge))/a2
        x2 = (-b2 - math.sqrt(judge))/a2
    if abs(b) < 1.0e-6:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1 and overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2 and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

def intersection(o1,o2):
    err = 1e-7
    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]
    judge = b2**2 - a2*c2
    if judge < 0:
        return None, None
    elif abs(judge) < err:
        x = -b2/a2
        if abs(b) < err:
            y = o1[1] + math.sqrt(1 - (x - o1[0])**2)
        else:
            y = -(a*x + c)/b
        return [x,y], None
    else:
        x1 = (-b2 + math.sqrt(judge))/a2
        x2 = (-b2 - math.sqrt(judge))/a2
    if abs(b) < err:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1 and overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2 and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

def intersection(o1,o2):
    err = 1e-5
    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]
    judge = b2**2 - a2*c2
    if judge < 0:
        return None, None
    elif abs(judge) < err:
        x = -b2/a2
        if abs(b) < err:
            y = o1[1] + math.sqrt(1 - (x - o1[0])**2)
        else:
            y = -(a*x + c)/b
        return [x,y], None
    else:
        x1 = (-b2 + math.sqrt(judge))/a2
        x2 = (-b2 - math.sqrt(judge))/a2
    if abs(b) < err:
        y1 = o1[1] + math.sqrt(1 - (x1 - o1[0])**2)
        y2 = o1[1] - math.sqrt(1 - (x1 - o1[0])**2)
    else:
        y1 = -(a*x1 + c)/b
        y2 = -(a*x2 + c)/b
    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 = 1
    for i in range(n - 1):
        for j in range(i + 1, n):
            if not overlap(p[i], p[j], 2):
                continue
            p1, p2 = intersection(p[i], p[j])
            cnt1 = 0
            cnt2 = 0
            for k in range(n):
                if p1 and overlap(p1, p[k], 1):
                    cnt1 += 1
                if p2 and overlap(p2, p[k], 1):
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

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

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:
                    cnt1 += 1
                if p2[0] and dist(p2, p[k]) <= 1:
                    cnt2 += 1
            ans = max([ans, cnt1, cnt2])
    print(ans)

Submission status: Wrong Answer

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.00 >= abs(q - p) for p in P) for q in Q] + [1]))

Submission status: Wrong Answer

Solution code:
import itertools
def isOverlapped(x1,y1,x2,y2,r1,r2):
    return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))**0.5<=r1+r2
while True:
    n=input()
    if n==0:
        break
    li=[]
    for i in xrange(n):
        li.append(map(float,raw_input().split(",")))
    ov=[1]*n
    for i,j in itertools.combinations(xrange(n),2):
        if isOverlapped(li[i][0],li[i][1],li[j][1],li[j][1],1,1):
            ov[i]+=1
            ov[j]+=1
    print max(ov)

Submission status: Wrong Answer

Solution code:
import itertools
def isOverlapped(x1,y1,x2,y2,r1,r2):
    return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))**0.5<=r1+r2+0.0
while True:
    n=input()
    if n==0:
        break
    li=[]
    for i in xrange(n):
        li.append(map(float,raw_input().split(",")))
    ov=[1]*n
    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):
            ov[i]+=1
            ov[j]+=1
    print max(ov)

Submission status: Wrong Answer

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.0
while True:
    n=input()
    if n==0:
        break
    li=[]
    for i in xrange(n):
        li.append(map(float,raw_input().split(",")))
    ma=0
    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)]]
            c=0
            for m in xrange(n):
                if isOverlapped(node[0][0],node[0][1],li[m][0],li[m][1],0,1):
                    c+=1
            ma=max(c,ma)
    print ma