Prozessoptimierung beim Bau
Sie wurden von einem Bauunternehmen engagiert, um den Prozess des Transports schwerer Baumaterialien innerhalb eines bestimmten Geländes zu optimieren.
Auf dem Baufeld gibt es ein rechteckiges Areal mit Breite
w und Höhe h. Man kann sich das wie ein Rechteck vorstellen, dessen untere linke Ecke bei den Koordinaten (0, 0) und dessen obere rechte Ecke bei (w, h) liegt. Der Eingang befindet sich in der Mitte der unteren Begrenzung des Baugeländes.Es sind
n Kräne auf dem Gelände verteilt, mit Koordinaten . Jeder Kran kann ein Material aufnehmen, sofern sich das Material in seinem Schwenkbereich befindet. Die Kräne können sich um 360° drehen und besitzen Reichweiten mit den Radien .Angenommen, Sie haben verschiedene Zielpunkte, an denen die Materialien abgeladen werden sollen. Das Unternehmen möchte wissen, wie viele Kräne mindestens benötigt werden, um das Material vom Eingang bis zu jedem dieser Zielpunkte zu transportieren.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
w und h (2 ≤ w, h ≤ 200), wobei w eine gerade Zahl ist.Die nächste Zeile enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 50), die die Anzahl der Kräne angibt.Die darauffolgenden
n Zeilen enthalten jeweils 3 ganze Zahlen – die Koordinaten eines Krans und seinen Reichweitenradius (0 ≤ ≤ w) (0 ≤ ≤ h) und (0 ≤ ≤ 200).Danach folgt eine Zeile mit einer einzelnen ganzen Zahl
k (1 ≤ k ≤ 30), die angibt, wie viele Zielpunkte es gibt.Die nächsten
k Zeilen umfassen je 2 ganze Zahlen (0 ≤ ≤ w) (0 ≤ ≤ h), also die Koordinaten der Zielpunkte.Ausgabe
Das Programm soll
k Zeilen ausgeben, in denen jeweils die minimale Anzahl von Kränen steht, die benötigt wird, um den jeweiligen Zielpunkt zu erreichen. Ist es unmöglich, einen Zielpunkt zu erreichen, soll das Programm „Impossible“ ausgeben.Beispiele
Eingabe | Ausgabe |
4 4
2
2 1 1
2 3 1
5
2 2
3 2
1 2
2 3
3 3 | 1
Impossible
Impossible
2
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB