#!/usr/bin/env python3 # Check to make sure steam cloud lies below the mountain horizon # (single-point touches are okay) # Check to make sure no two consecutive segments are collinear (not # that it should matter). # Does not do basic checks on input bounds, etc. import sys import math # Circle/segment intersection code adapted from stack overflow. Includes # "intersections" where entire segment is interior to circle. # # https://stackoverflow.com/questions/67116296/is-this-code-for-determining-if-a-circle-and-line-segment-intersects-correct # # Modified to identify and return a pair of booleans [b1,b2], where # b1 = "interior intersection" and b2 = "endpoint intersection" def inter(x1, y1, x2, y2, circx, circy, r): x_linear = x2 - x1 x_constant = x1 - circx y_linear = y2 - y1 y_constant = y1 - circy a = x_linear * x_linear + y_linear * y_linear half_b = x_linear * x_constant + y_linear * y_constant c = x_constant * x_constant + y_constant * y_constant - r * r # Grazes circle if smaller solution == 1: single = False if half_b*half_b >= a*c: # Too bad I had to introduce a sqrt here! Original code didn't need # to find the actual solutions, only whether or not there was a collision t = (-half_b - math.sqrt(half_b * half_b - a * c))/a single = abs(t-1)<= 1e-9 return [\ half_b * half_b >= a * c and\ (-half_b <= a or c + half_b + half_b + a <= 0) and\ # I THINK the following change eliminates endpoint intersections: # (half_b <= 0 or c <= 0),single] # Original code (half_b < 0 or c < 0),single] # My modification # Returns True iff segments i and i+1 are collinear def col(i): return x[i] * (y[i+1] - y[i+2]) +\ x[i+1] * (y[i+2] - y[i]) +\ x[i+2] * (y[i] - y[i+1]) == 0 line = list(map(int,sys.stdin.readline().split())) n = line[0] x = [None for i in range(n+1)] y = [None for i in range(n+1)] for i in range(n+1): x[i] = line[2*i+1] y[i] = line[2*i+2] [cx,sx,sy,rad,dx,dy,vel] = list(map(int,sys.stdin.readline().split())) # See if any consecutive collinear segments: for i in range(n-1): if col(i): # print(f'at point[{i}]: collinear segments') sys.exit(43) # See if any line intersects the circle: for i in range(n): [intsec,single] = inter(x[i],y[i],x[i+1],y[i+1],sx,sy,rad) # These four lines just for debugging: # if intsec: # print(f'({x[i]},{y[i]}) - ({x[i+1]},{y[i+1]}) intersects') # if single: # print("(single point)") if intsec and not single: sys.exit(43) # Make sure circle lies below the line and not above it. # Only need to do this if some portion of the circle lies between # x[i] and x[i+1] if (x[i]-rad >= sx) or (x[i+1]+rad <= sx): continue if (sy <= min(y[i],y[i+1])): continue # easy case # Can still be below even if center lies above one of the points: if (not intsec) or single: pdx = x[i+1]-x[i] # delta x of the directed line pdy = y[i+1]-y[i] # delta y of the directed line spx = sx - x[i] # directed x dist from circle center to p[i] spy = sy - y[i] # directed y dist from circle center to p[i] det = -pdx*pdx-pdy*pdy t = (pdx*spy-pdy*spx)/det if t < 0: sys.exit(43) sys.exit(42)