QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73402 | #5155. Faster Than Light | XinWoa | RE | 0ms | 0kb | Python3 | 3.9kb | 2023-01-25 04:36:02 | 2023-01-25 04:36:05 |
Judging History
answer
# Hier sind die Methoden für die Konvexe Hülle
# Nimmt 3 Punkte entgegen und bildet das Kreuzprodukt von Vektor point_b-point_a und Vektor point_c-point_a
def cross(point_a, point_b, point_c):
vec_ab = ((point_b[0] - point_a[0]), (point_b[1] - point_a[1]))
vec_ac = ((point_c[0] - point_a[0]), (point_c[1] - point_a[1]))
return (vec_ab[0] * vec_ac[1]) - (vec_ab[1] * vec_ac[0])
def form_lower_hull(all_points):
# Punkte werden erst nach x, dann nach y sortiert
all_points = sorted(all_points, key=lambda element: (element[0], element[1]))
sol = []
for c in all_points:
# Nächster Punkt wird dem Solution Array angehangen
sol.append(c)
# Immer wenn es mindestens 3 Punkte im Solution Array gibt, überprüfe die letzten 3
while len(sol) > 2 and cross(sol[-3], sol[-2], sol[-1]) < 0:
# Falls die Richtung mit dem Uhrzeigersinn geht, dann muss der vorletzte Punkt raus
sol.pop(-2)
return sol
def form_upper_hull(all_points):
# Punkte werden absteigend nach x und dann y Wert sortiert
all_points = sorted(all_points, key=lambda element: (-element[0], -element[1]))
sol = []
for c in all_points:
# Punkt wird dem Solution Array angehangen
sol.append(c)
# Immer wenn es mindestens 3 Punkte im Solution Array gibt, überprüfe die letzten 3 Punkte
while len(sol) > 2 and cross(sol[-3], sol[-2], sol[-1]) < 0:
# Falls die Richtung mit dem Uhrzeigersinn geht, dann muss der vorletzte Punkt raus
sol.pop(-2)
sol.reverse()
return sol
# Scanne von links nach rechts und schaue, ob die Punkte jeweils links oder rechts von den Linien der
# Konvexen Hülle liegen
def overlap(upper_hull, lower_hull):
# Setze Pointer auf den Anfang (ganz links)
lower_pointer, upper_pointer = 0, 0
# Schleife läuft so lange, bis beide Pointer ihr Ende erreicht haben
while lower_pointer < len(lower_hull)-1 or upper_pointer < len(upper_hull)-1:
# Bitte funktionier einfach
if (upper_pointer < len(upper_hull) - 1 and lower_hull[lower_pointer][0] > upper_hull[upper_pointer][0]):
if upper_hull[upper_pointer][0] <= lower_hull[lower_pointer][0] <= upper_hull[upper_pointer + 1][0]:
if cross(lower_hull[lower_pointer], upper_hull[upper_pointer], upper_hull[upper_pointer + 1]) > 0:
return True
upper_pointer += 1
else:
if lower_hull[lower_pointer][0] <= upper_hull[upper_pointer][0] <= lower_hull[lower_pointer + 1][0]:
if cross(upper_hull[upper_pointer], lower_hull[lower_pointer + 1], lower_hull[lower_pointer]) > 0:
return True
lower_pointer += 1
return False
n = int(input())
# Input wird eingelesen und in eine Liste gepackt, in der jeweils die Ecken für jede Box stehen
boxes = []
for a in range(n):
x1, y1, x2, y2 = map(int, input().split())
first = (x1, y1)
second = (x2, y2)
boxes.append([first, second])
# Listen für die Konvexen Hüllen werden deklariert
all_convex_hulls, upper_right, upper_left, lower_right, lower_left = [], [], [], [], []
for a in boxes:
upper_right.append(a[1])
upper_left.append((a[0][0], a[1][1]))
lower_right.append((a[1][0], a[0][1]))
lower_left.append(a[0])
all_convex_hulls.append(form_lower_hull(upper_right))
all_convex_hulls.append(form_lower_hull(upper_left))
all_convex_hulls.append(form_upper_hull(lower_right))
all_convex_hulls.append(form_upper_hull(lower_left))
# Die Konvexen Hüllen werden auf Überlappung überprüft
possible_negative = overlap(all_convex_hulls[0], all_convex_hulls[3])
possible_positive = overlap(all_convex_hulls[1], all_convex_hulls[2])
if possible_negative and possible_positive:
print("impossible")
else:
print("possible")
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
5 1 3 3 4 2 2 4 3 4 1 5 3 5 2 7 3 6 3 8 4