This is an example of the answer to the 2014 summer hospital exam. Problem link
--Recursion --Containance of polygonal points
(1)
from numpy import sqrt
# (1
def R0_num(d):
return (int(10.0 / d) + 1)**2
(2)
def checkInside(x, y):
return abs(x - 5.0)**2 + abs(y - 5.0)**2 <= 25.0
def R1_num(d):
ret = 0
col = row = int(10.0 / d) + 1
for i in range(0, col):
for j in range(0, row):
if (checkInside(i * d, j * d)):
ret += 1
return ret
def solve(d):
return (R1_num(d) / R0_num(d)) * 0.25
(3), (4)
def solve(n):
tmp_tri_area = 25.0 * sqrt(3.0)
ret = tmp_tri_area
increase = 3
for i in range(0, n):
tmp_tri_area /= 9
ret += tmp_tri_area * increase
increase *= 4
return ret
(5), (6) --Computational complexity O ((-5√3 / 3 <= y <= 5√3 and 0 <= x <= 10 grids) * (number of edges: 3 * 4 ^ n)) Even if d = 1.0, the limit is n = 7 (in c ++, it may be possible to go up to about 9, but the standard is about 2 seconds) ――There may be a better way to solve this problem, but I couldn't think of it in time, so I did this. --The Cordinate module is [Spiral Book](https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83% 9F% E3% 83% B3% E3% 82% B0% E3% 82% B3% E3% 83% B3% E3% 83% 86% E3% 82% B9% E3% 83% 88% E6% 94% BB% E7% 95% A5% E3% 81% AE% E3% 81% 9F% E3% 82% 81% E3% 81% AE% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E3% 81% A8% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0-% E6% B8% A1% E9% 83% A8-% E6% 9C% 89% E9% 9A% 86 / dp / 4839952957 / ref = sr_1_1? __mk_ja_JP =% E3% 82% AB% E3% 82% BF % E3% 82% AB% E3% 83% 8A & crid = 38GPK1WUNFWCB & keywords =% E3% 82% A2% E3% 83% AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% E3% 83% A0% E3% 81% A8% E3% 83% 87% E3% 83% BC% E3% 82% BF% E6% A7% 8B% E9% 80% A0 & qid = 1572863419 & sprefix =% E3% 82% A2% E3% 83 % AB% E3% 82% B4% E3% 83% AA% E3% 82% BA% 2Caps% 2C227 & sr = 8-1) The author customized it for the hospital trial by referring to Chapter 16, so it will be released for the time being. I will do it after the hospital exam. (But basically, I just implemented Chapter 16 of the spiral book in python as it is.)
import sys
sys.path.append('..')
from Cordinate import *
def koch_points(n, p1, p2):
ret = []
def koch(n, p1, p2):
if (n == 0):
return
s = p1 + (p2 - p1) / 3
u = p1 + 2 * (p2 - p1) / 3
t = rotate(u, s, 60)
koch(n - 1, p1, s)
ret.append(s)
koch(n - 1, s, t)
ret.append(t)
koch(n - 1, t, u)
ret.append(u)
koch(n - 1, u, p2)
koch(n, p1, p2)
ret.insert(0, p1)
ret.append(p2)
return ret
def solve(d, n):
p1 = Point(0, 0)
p2 = Point(5, 5 * sqrt(3))
p3 = Point(10, 0)
polygon = []
tmp1 = koch_points(n, p1, p2)
polygon.extend(tmp1)
polygon.pop(-1)
tmp2 = koch_points(n, p2, p3)
polygon.extend(tmp2)
polygon.pop(-1)
tmp3 = koch_points(n, p3, p1)
polygon.extend(tmp3)
polygon.pop(-1)
check_points = []
#Number of line spacings in the negative direction
negative_rows = int((5 * sqrt(3) / 3) / d + 1e-12)
#Number of line spacings in the positive direction
positive_rows = int(5 * sqrt(3) / d + 1e-12)
#Number of column spacings
columns = int(10 / d + 1e-12)
#Check the grid in the negative y-axis direction_Added to points (not including x-axis)
for i in range(1, negative_rows+1):
for j in range(0, columns+1):
check_p = Point(d * j, -(d * i))
check_points.append(check_p)
#Check the y-axis positive grid_Added to points (including x-axis)
for i in range(0, positive_rows+1):
for j in range(0, columns+1):
check_p = Point(d * j, d * i)
check_points.append(check_p)
ret = 0
for i in range(0, len(check_points)):
point = check_points[i]
if (contains(polygon, point) > 0):
ret += 1
return ret
If you disregard the amount of calculation, it will be easier to write in c ++ for the competition professionals, or it may be completed in about an hour for people who are blue coders or higher. Conversely, I think that (5) and (6) cannot do anything without knowing how to solve the inclusion of points, so I think this year is an algorithm-oriented year.
Recommended Posts