-
Notifications
You must be signed in to change notification settings - Fork 7
/
cutting_cake.py
67 lines (61 loc) · 2.59 KB
/
cutting_cake.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Virtual World Finals - Problem A. Cutting Cake
# https://codingcompetitions.withgoogle.com/codejam/round/0000000000436329/000000000084fba1
#
# Time: O(NlogN)
# Space: O(N)
#
from fractions import Fraction
def ccw(A, B, C):
return (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])
def find_delta_slopes(points):
delta_slopes = [Fraction(0)]*3
for i in xrange(len(points)):
if not points[i][0]-points[i-1][0]:
continue
slope = Fraction(points[i][1]-points[i-1][1], points[i][0]-points[i-1][0])
delta_slopes[i-1] += slope
delta_slopes[i] -= slope
assert(sum(delta_slopes) == 0)
return delta_slopes
def cutting_cake():
N, W, H = map(int, raw_input().strip().split())
P, Q, R, S = map(Fraction, raw_input().strip().split())
points = sorted([(Fraction(0), Fraction(0)), (P, Q), (R, S)])
prev_diff, area = Fraction(0), Fraction(-ccw(*points), 2)
events = []
for _ in xrange(N):
X, Y, A, B = map(Fraction, raw_input().strip().split())
prev_diff -= B*area
for i in xrange(len(points)):
events.append((X+points[i][0], i, A+B))
events.sort()
result = abs(prev_diff)
delta_y = [points[i][1]-points[i-1][1] if points[i-1][0] == points[i][0] else 0 for i in xrange(len(points))]
delta_slopes = find_delta_slopes(points)
prev_x = prev_y = slope = Fraction(0)
for curr_x, i, w in events:
dx = curr_x-prev_x
if not dx:
prev_y += w*delta_y[i]
slope += w*delta_slopes[i]
continue
curr_y = prev_y+dx*slope
curr_diff = prev_diff+(prev_y+curr_y)/2*dx
result = min(result, abs(curr_diff)) # the values at each endpoint of the interval
extreme_diff = prev_diff
if curr_y*prev_y < 0: # find the value at the extreme point of the quadratic if that's within the interval
extreme_y = Fraction(0)
extreme_x = (extreme_y-prev_y)/slope+prev_x
extreme_diff = prev_diff+(prev_y+extreme_y)/2*(extreme_x-prev_x)
result = min(result, abs(extreme_diff))
if min(extreme_diff, prev_diff, curr_diff) <= 0 <= max(extreme_diff, prev_diff, curr_diff): # whether the quadratic crosses 0 within the interval
result = Fraction(0)
break
prev_diff, prev_x, prev_y = curr_diff, curr_x, curr_y
slope += w*delta_slopes[i]
result /= abs(area)
return "%s/%s"%(result.numerator, result.denominator)
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, cutting_cake())