Skip to content

Instantly share code, notes, and snippets.

@kg86
Created August 31, 2014 02:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kg86/f2da35d0eafbf23ffc34 to your computer and use it in GitHub Desktop.
Save kg86/f2da35d0eafbf23ffc34 to your computer and use it in GitHub Desktop.
#! -*- 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment