import math
EPS = 1E-9
class Pt:
def __init__(self, x, y):
self.x = x
self.y = y
def __lt__(self, other):
return self.x < other.x - EPS or (abs(self.x - other.x) < EPS and self.y < other.y - EPS)
def __repr__(self):
return f"Point({self.x}, {self.y})"
class Line:
def __init__(self, p=None, q=None):
if p and q:
self.a = p.y - q.y
self.b = q.x - p.x
self.c = -self.a * p.x - self.b * p.y
self.norm()
else:
self.a = self.b = self.c = 0.0
def norm(self):
z = math.sqrt(self.a ** 2 + self.b ** 2)
if abs(z) > EPS:
self.a /= z
self.b /= z
self.c /= z
def dist(self, p):
return self.a * p.x + self.b * p.y + self.c
def det(a, b, c, d):
return a * d - b * c
def betw(l, r, x):
return min(l, r) <= x + EPS and x <= max(l, r) + EPS
def intersect_1d(a, b, c, d):
if a > b:
a, b = b, a
if c > d:
c, d = d, c
return max(a, c) <= min(b, d) + EPS
def intersect(a, b, c, d):
if not (intersect_1d(a.x, b.x, c.x, d.x) and intersect_1d(a.y, b.y, c.y, d.y)):
return False, None, None
m = Line(a, b)
n = Line(c, d)
zn = det(m.a, m.b, n.a, n.b)
if abs(zn) < EPS:
if abs(m.dist(c)) > EPS or abs(n.dist(a)) > EPS:
return False, None, None
if b < a:
a, b = b, a
if d < c:
c, d = d, c
left = max(a, c)
right = min(b, d)
return True, left, right
else:
x = -det(m.c, m.b, n.c, n.b) / zn
y = -det(m.a, m.c, n.a, n.c) / zn
left = right = Pt(x, y)
if (betw(a.x, b.x, left.x) and betw(a.y, b.y, left.y) and
betw(c.x, d.x, left.x) and betw(c.y, d.y, left.y)):
return True, left, right
return False, None, None
def rotate(p, t):
x = p.x * math.cos(t * math.pi / 180) - p.y * math.sin(t * math.pi / 180)
y = p.x * math.sin(t * math.pi / 180) + p.y * math.cos(t * math.pi / 180)
return Pt(x, y)
def covered_dots(w, h, t):
t %= 360
A = Pt(w / 2, h / 2)
B = Pt(w / 2, -h / 2)
C = Pt(-w / 2, -h / 2)
D = Pt(-w / 2, h / 2)
rA, rB, rC, rD = map(lambda p: rotate(p, t), (A, B, C, D))
xmin = math.floor(min([p.x for p in (rA, rB, rC, rD)])) - 1
xmax = math.ceil(max([p.x for p in (rA, rB, rC, rD)])) + 1
ymin = math.ceil(min([p.y for p in (rA, rB, rC, rD)]))
ymax = math.floor(max([p.y for p in (rA, rB, rC, rD)]))
ans = 0
r = 0
for y in range(ymax + 1):
uniq = set()
for p1, p2 in ((rA, rB), (rB, rC), (rC, rD), (rD, rA)):
p3, p4 = Pt(xmin, y), Pt(xmax, y)
b, left, right = intersect(p1, p2, p3, p4)
if b:
uniq.add(round(left.x, 5))
xs = list(uniq)
if len(xs) == 2:
x1, x2 = min(xs[0], xs[1]), max(xs[0], xs[1])
add = math.floor(x2) - math.ceil(x1) + 1
else:
add = 1
if y > 0:
ans += add
else:
r += add
return r + 2 * ans
r1 = covered_dots(6, 4, 45)
r2 = covered_dots(3, 2, 45)
print(r1, r2)
To embed this program on your website, copy the following code and paste it into your website's HTML: