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-unix -*-
import sys

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

if __name__=='__main__':
  lines = [x.strip() for x in sys.stdin.readlines() if x != '' and x != '\n']
  # print lines
  # print lines[1:-1]
  # print [x.split(',') for x in lines[1:-1]]
  ps = [map(float, x.split(',')) for x in lines[1:-1]]
  n = int(lines[0])
  count = [x for x in range(n)]
  for i in range(n):
    changes = set([i])
    changeto = i
    for j in range(i+1, n):
      # print (i, j), 
      if overlap(ps[i], ps[j]):
        if count[j] != -1:
          changeto = min(changeto, count[j])
          changes.add(count[j])
    for j in range(n):
      if count[j] in changes:
        count[j] = changeto
  # print range(n)
  # print count

  num = [0 for x in range(n)]
  for i in count:
    num[i] += 1
  print max(num)

Submission status: Wrong Answer

Solution code:
import math
while True:
    n = input()
    if (n == 0):
        break
    d = []
    for i in range(n):
        a = map(float, raw_input().split(","))
        y = a[0]
        x = a[1]
        d.append([y,x])
    ans = 0
    for i in range(n):
        sheets = 1
        for j in range(i + 1, n):
            dist = math.sqrt((d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2)
            if (dist <= 2.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

Solution code:
import math
while True:
    n = input()
    if (n == 0):
        break
    d = []
    for i in range(n):
        a = map(float, raw_input().split(","))
        y = a[0]
        x = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = math.sqrt((d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2)
            if (dist <= 2.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

Solution code:
import math
while True:
    n = input()
    if (n == 0):
        break
    d = []
    for i in range(n):
        a = map(float, raw_input().split(","))
        y = a[0]
        x = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = (d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2
            if (dist <= 4.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

Solution code:
import math
while True:
    n = input()
    if (n == 0):
        break
    d = []
    for i in range(n):
        a = map(float, raw_input().split(","))
        y = a[0]
        x = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = (d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2
            format(dist, ".12g")
            if (dist <= 4.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

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

    for i in range(n):
        a = map(float, raw_input().split(","))
        x = a[0]
        y = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = (d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2
            format(dist, ".12g")
            if (dist + EPS<= 4.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

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

    for i in range(n):
        a = map(float, raw_input().split(","))
        x = a[0]
        y = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = (d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2
            format(dist, ".12g")
            if (dist <= 4.0 + EPS):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

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

    for i in range(n):
        a = map(float, raw_input().split(","))
        x = a[0]
        y = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = (d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2
            format(dist, ".12g")
            if (dist <= 4.0 + EPS):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

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

    for i in range(n):
        a = map(float, raw_input().split(","))
        x = a[0]
        y = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = (d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2
            format(dist, ".12g")
            if (dist + EPS <= 4.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

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

    for i in range(n):
        a = map(float, raw_input().split(","))
        x = a[0]
        y = a[1]
        d.append([y,x])
    ans = 1
    for i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = math.sqrt((d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2)
            format(dist, ".12g")
            if (dist <= 2.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

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 i in range(n):
        sheets = 1
        for j in range(n):
            if (i == j):continue
            dist = math.sqrt((d[i][0] - d[j][0]) ** 2  + (d[i][1] - d[j][1]) ** 2)
            format(dist, ".12g")
            if (dist + EPS <= 2.0):
                sheets += 1
        ans = max(ans, sheets)
    print ans

Submission status: Wrong Answer

Solution code:
import math
n = input()
pos = [map(float, raw_input().split(",")) for i in xrange(n)]
ans = 0
px = [0.0]*2; py = [0.0]*2
sig = [1.0, -1.0]
for i in xrange(n):
    for j in xrange(i+1, n):
        rx = pos[j][0] - pos[i][0]
        ry = pos[j][1] - pos[i][1]
        l = math.sqrt(rx**2 + ry**2)/2.0
        if l>1.000000000:
            continue
        lr = math.sqrt(1-l**2)
        for s in xrange(2):
            if l>0.0:
                px[s] = (l*rx - sig[s]*lr*ry)/(2.0*l) + pos[i][0]
                py[s] = (l*ry + sig[s]*lr*rx)/(2.0*l) + pos[i][1]
            else:
                px[s] = pos[i][0]
                py[s] = pos[i][1]
        count = 2
        for k in xrange(n):
            if k==i or k==j:
                continue
            for s in xrange(2):
                dd = (pos[k][0] - px[s])**2 + (pos[k][1] - py[s])**2
                if dd < 1.000000001:
                    count += 1
                    break
        ans = max(ans, count)
print ans

Submission status: Wrong Answer

Solution code:
import math
n = input()
pos = [map(float, raw_input().split(",")) for i in xrange(n)]
ans = 0
px = [0.0]*2; py = [0.0]*2
sig = [1.0, -1.0]
for i in xrange(n):
    for j in xrange(i+1, n):
        rx = pos[j][0] - pos[i][0]
        ry = pos[j][1] - pos[i][1]
        l = math.sqrt(rx**2 + ry**2)/2.0
        if l>1.000000000:
            continue
        lr = math.sqrt(1-l**2)
        for s in xrange(2):
            if l>0.0:
                px[s] = (l*rx - sig[s]*lr*ry)/(2.0*l) + pos[i][0]
                py[s] = (l*ry + sig[s]*lr*rx)/(2.0*l) + pos[i][1]
            else:
                px[s] = pos[i][0]
                py[s] = pos[i][1]
        count = 2
        for k in xrange(n):
            if k==i or k==j:
                continue
            for s in xrange(2):
                dd = (pos[k][0] - px[s])**2 + (pos[k][1] - py[s])**2
                if dd < 1.001000:
                    count += 1
                    break
        ans = max(ans, count)
print ans

Submission status: Wrong Answer

Solution code:
import math
n = input()
pos = [map(float, raw_input().split(",")) for i in xrange(n)]
ans = 0
for i in xrange(n):
    for j in xrange(i+1, n):
        rx = pos[j][0] - pos[i][0]
        ry = pos[j][1] - pos[i][1]
        if rx**2 + ry**2 > 4.0:
            continue
        l = math.sqrt(rx**2 + ry**2)/2.0
        lr = math.sqrt(1.0-l**2)
        for sig in [1.0, -1.0]:
            if l>0.0:
                px = (l*rx - sig*lr*ry)/(2.0*l) + pos[i][0]
                py = (l*ry + sig*lr*rx)/(2.0*l) + pos[i][1]
            else:
                px = pos[i][0]
                py = pos[i][1]
            count = 2
            for k in xrange(n):
                if k==i or k==j:
                    continue
                dd = (pos[k][0] - px)**2 + (pos[k][1] - py)**2
                if dd < 1.0000001:
                    count += 1
            ans = max(ans, count)
print ans

Submission status: Wrong Answer

Solution code:
import math
n = input()
pos = [map(float, raw_input().split(",")) for i in xrange(n)]
ans = 0
for i in xrange(n):
    for j in xrange(i+1, n):
        rx = pos[j][0] - pos[i][0]
        ry = pos[j][1] - pos[i][1]
        if rx**2 + ry**2 > 4.0 or rx == ry == 0.0:
            continue
        l = math.sqrt(rx**2 + ry**2)/2.0
        lr = math.sqrt(1.0-l**2)
        for sig in ([1.0, -1.0] if l<1.0 else [1.0]):
            if l<1.0:
                px = (l*rx - sig*lr*ry)/(2.0*l) + pos[i][0]
                py = (l*ry + sig*lr*rx)/(2.0*l) + pos[i][1]
            else:
                px = (pos[i][0] + pos[j][0])/2.0
                px = (pos[i][1] + pos[j][1])/2.0
            count = 2
            for k in xrange(n):
                if k==i or k==j:
                    continue
                dd = (pos[k][0] - px)**2 + (pos[k][1] - py)**2
                if dd < 1.0000001:
                    count += 1
            ans = max(ans, count)
print ans

Submission status: Wrong Answer

Solution code:
from functools import reduce

n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]

overlapable = [set(i for i, (x2, y2) in enumerate(seals) if (x2 - x1) ** 2 + (y2 - y1) ** 2 <= 4)
               for (x1, y1) in seals]

print(max(len(reduce(lambda cur, sid: cur & overlapable[sid], oll, oll.copy())) for oll in overlapable))

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


def count_in_circle(p1, p2, cx, cy):
    return


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-9

max_count = 0

for p1, p2 in combinations(range(n), 2):
    l = dist_square_id(p1, p2)
    if l + eps > 4:
        continue
    l **= 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - l ** 2 / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        count1 += dist_square(seals[i][0], seals[i][1], cx1, cy1) <= 1 + eps
        count2 += dist_square(seals[i][0], seals[i][1], cx2, cy2) <= 1 + eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-6

max_count = 0

for p1, p2 in combinations(range(n), 2):
    l = dist_square_id(p1, p2)
    if l + eps > 4:
        continue
    l **= 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - l ** 2 / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        count1 += dist_square(tx, ty, cx1, cy1) < 1 + eps
        count2 += dist_square(tx, ty, cx2, cy2) < 1 + eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-6

max_count = 0

for p1, p2 in combinations(range(n), 2):
    l = dist_square_id(p1, p2)
    if l + eps > 4:
        continue
    l **= 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - l ** 2 / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        count1 += dist_square(tx, ty, cx1, cy1) - 1 < eps
        count2 += dist_square(tx, ty, cx2, cy2) - 1 < eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-6
max_count = 0

for p1, p2 in combinations(range(n), 2):
    ls = dist_square_id(p1, p2)
    if ls - 4 > eps:
        continue
    l = ls ** 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - ls / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        print(p1, p2, i, cx1, cy1, cx2, cy2, dist_square(tx, ty, cx1, cy1) ** 0.5, dist_square(tx, ty, cx2, cy2) ** 0.5)
        count1 += dist_square(tx, ty, cx1, cy1) - 1 < eps
        count2 += dist_square(tx, ty, cx2, cy2) - 1 < eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-6
max_count = 0

for p1, p2 in combinations(range(n), 2):
    ls = dist_square_id(p1, p2)
    if ls > 4 - eps:
        continue
    l = ls ** 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - ls / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        print(p1, p2, i, cx1, cy1, cx2, cy2, dist_square(tx, ty, cx1, cy1) ** 0.5, dist_square(tx, ty, cx2, cy2) ** 0.5)
        count1 += dist_square(tx, ty, cx1, cy1) - 1 < eps
        count2 += dist_square(tx, ty, cx2, cy2) - 1 < eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-6
max_count = 1

for p1, p2 in combinations(range(n), 2):
    ls = dist_square_id(p1, p2)
    if ls > 4 - eps:
        continue
    l = ls ** 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - ls / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        print(p1, p2, i, cx1, cy1, cx2, cy2, dist_square(tx, ty, cx1, cy1) ** 0.5, dist_square(tx, ty, cx2, cy2) ** 0.5)
        count1 += dist_square(tx, ty, cx1, cy1) - 1 < eps
        count2 += dist_square(tx, ty, cx2, cy2) - 1 < eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def memorize(f):
    memo = {}

    def helper(p1, p2):
        key = (p1, p2)
        if key in memo:
            return memo[key]
        res = f(p1, p2)
        memo[key] = res
        memo[(p2, p1)] = res
        return res

    return helper


@memorize
def dist_square_id(p1, p2):
    (x1, y1) = seals[p1]
    (x2, y2) = seals[p2]
    return dist_square(x1, y1, x2, y2)


def dist_square(x1, y1, x2, y2):
    return (x2 - x1) ** 2 + (y2 - y1) ** 2


n = int(input())
seals = [tuple(map(float, input().split(','))) for _ in range(n)]
eps = 1e-6
max_count = 1

for p1, p2 in combinations(range(n), 2):
    ls = dist_square_id(p1, p2)
    if ls > 4 - eps:
        continue
    l = ls ** 0.5
    x1, y1 = seals[p1]
    x2, y2 = seals[p2]
    mx, my = (x1 + x2) / 2, (y1 + y2) / 2
    dx, dy = x2 - x1, y2 - y1
    hl = (1 - ls / 4) ** 0.5
    nx, ny = -dy * hl / l, dx * hl / l
    cx1, cy1 = mx + nx, my + ny
    cx2, cy2 = mx - nx, my - ny

    count1 = count2 = 2
    for i in range(n):
        if i == p1 or i == p2:
            continue
        tx, ty = seals[i]
        count1 += dist_square(tx, ty, cx1, cy1) - 1 < eps
        count2 += dist_square(tx, ty, cx2, cy2) - 1 < eps

    max_count = max(max_count, count1, count2)

print(max_count)

Submission status: Wrong Answer

Solution code:
def judge(x1,y1,x2,y2):
	distance=((x1-x2)**2+(y1-y2)**2)**0.5
	if distance>2:
		return False
	else:
		return True

while True:
	n=int(input())
	if n==0:break
	P=[]
	Overlap=[0]*n
	for i in range(n):
		x,y=map(float,input().split(','))
		P.append((x,y))
	for i in range(n):
		for j in range(n):
			if judge(P[i][0],P[i][1],P[j][0],P[j][1]):
				Overlap[i]+=1
	Overlap.sort()
	print(Overlap[-1])

Submission status: Wrong Answer

Solution code:
def judge(x1,y1,x2,y2):
	distance=((x1-x2)**2+(y1-y2)**2)**0.5
	if distance>2:
		return False
	else:
		return True

while True:
	n=int(input())
	if n==0:break
	P=[]
	Overlap=[0]*n
	for i in range(n):
		x,y=map(float,input().split(','))
		P.append((x,y))
	for i in range(n):
		for j in range(n):
			if judge(P[i][0],P[i][1],P[j][0],P[j][1]):
				Overlap[i]+=1
	
	max=0
	for i in Overlap:
		if Overlap.count(i)==i:
			max=i
	print(max)

Submission status: Wrong Answer

Solution code:
def judge(x1,y1,x2,y2):
	distance=((x1-x2)**2+(y1-y2)**2)**0.5
	if distance>2:
		return False
	else:
		return True

while True:
	n=int(input())
	if n==0:break
	P=[]
	Overlap=[0]*n
	for i in range(n):
		x,y=map(float,input().split(','))
		P.append((x,y))
	for i in range(n):
		for j in range(n):
			if judge(P[i][0],P[i][1],P[j][0],P[j][1]):
				Overlap[i]+=1
	
	max=0
	for i in Overlap:
		if Overlap.count(i)==i:
			if max<i:
				max=i
	print(max)

Submission status: Wrong Answer

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:
                        mxc=tuple(sorted(creek+(p,)))
                        if mxc not in newmaxcreek:
                            newmaxcreek.append(mxc)
            if len(newmaxcreek)==0:
                print max(map(len,maxcreek))
                break
            else:
                maxcreek=newmaxcreek[:]

Submission status: Wrong Answer

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]
                ptmp=()
                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:
                        ptmp+=(p,)
                if len(ptmp)>0:
                    mxc=tuple(sorted(creek+ptmp))
                    if mxc not in newmaxcreek:
                        newmaxcreek.append(mxc)
            if len(newmaxcreek)==0:
                print max(map(len,maxcreek))
                break
            else:
                maxcreek=newmaxcreek[:]

Submission status: Wrong Answer

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]
                ptmp=()
                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:
                        for pp in ptmp:
                            if p not in graphlist[pp]:
                                break
                        else:
                            ptmp+=(p,)
                if len(ptmp)>0:
                    mxc=tuple(sorted(creek+ptmp))
                    if mxc not in newmaxcreek:
                        newmaxcreek.append(mxc)
            if len(newmaxcreek)==0:
                print max(map(len,maxcreek))
                break
            else:
                maxcreek=newmaxcreek[:]

Submission status: Wrong Answer

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

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]
                ptmp=()
                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:
                        for pp in ptmp:
                            if p not in graphlist[pp]:
                                break
                        else:
                            ptmp+=(p,)
                if len(ptmp)>0:
                    mxc=tuple(sorted(creek+ptmp))
                    if mxc not in newmaxcreek:
                        newmaxcreek.append(mxc)
            if len(newmaxcreek)==0:
                print max(map(len,maxcreek))
                break
            else:
                maxcreek=newmaxcreek[:]

Submission status: Wrong Answer

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

import sys
import os
import math

n = int(input())
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: 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(0)