QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73402#5155. Faster Than LightXinWoaRE 0ms0kbPython33.9kb2023-01-25 04:36:022023-01-25 04:36:05

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-25 04:36:05]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-01-25 04:36:02]
  • 提交

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")

詳細信息

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

output:


result: