I cannot figure out what test case your code will fail, but I was able to
fix your problem
The problem is with floating point arithmetic. Because this problem
requires very precise calculation, you should avoid using floating point at
all
Please check out the following code that would pass both test cases:
*def gcd(a, b):*
* if a < 0:*
* a = -a*
* if b < 0:*
* b = -b*
* while b > 0:*
* a, b = b, a % b*
* return a*
*def main():*
* N = int(input())*
* holes = []*
* for i in range(N):*
* a = [int(x) for x in input().split()]*
* holes.append(tuple(a))*
* if N <= 4:*
* return N*
* slants = {}*
* actual_lines = {}*
* for cur_hole in holes:*
* for j in holes:*
* if j == cur_hole:*
* continue*
* dy = cur_hole[1] - j[1]*
* dx = cur_hole[0] - j[0]*
* g = gcd(dx, dy)*
* dy = dy // g*
* dx = dx // g*
* if dx < 0:*
* dx, dy = -dx, -dy*
* slant = (dx, dy)*
* slants.setdefault(slant, [set(), 2])*
* slants[slant][0].add(cur_hole)*
* slants[slant][0].add(j)*
* a = slants[max(slants, key=lambda x: len(slants[x][0]) +
(len(slants[x][0])%2==0))]*
* a = len(a[0]) + (len(a[0])%2==0)*
* return min(N, max(a+1,4))*
*num_of_cases = [int(x) for x in input().split()][0]*
*for p in range(num_of_cases):*
* output = main()*
* print("Case #{0}: {1}".format(p + 1, output))*
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/90f13cca-5331-442b-9941-0917223a704e%40googlegroups.com.
