211 lines
6.6 KiB
Python
211 lines
6.6 KiB
Python
#!/usr/bin/env python3
|
|
"""
|
|
Solveur Ad-Hoc avec Rotation 3D Support
|
|
Heuristique gloutonne basée sur tri LIFO + points candidats avec 6 orientations possibles
|
|
"""
|
|
|
|
import sys
|
|
from itertools import permutations
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# STRUCTURES DE DONNÉES
|
|
# ---------------------------------------------------------------------------
|
|
|
|
class Item:
|
|
def __init__(self, id, l, w, h, d):
|
|
self.id = id
|
|
self.original_dims = (l, w, h) # Dimensions originales (immutables)
|
|
self.dims = [l, w, h] # Dimensions actuelles [Longueur (x), Largeur (y), Hauteur (z)]
|
|
self.d = d # Ordre de livraison (-1 = indifférent)
|
|
self.position = None # (x, y, z)
|
|
self.vehicle_id = -1
|
|
self.rotation = (0, 1, 2) # Permutation appliquée (index dans original_dims)
|
|
|
|
# Heuristique de tri pour la League Or
|
|
if self.d == -1:
|
|
self.sort_d = 9999999
|
|
else:
|
|
self.sort_d = self.d
|
|
|
|
@property
|
|
def volume(self):
|
|
return self.dims[0] * self.dims[1] * self.dims[2]
|
|
|
|
def set_rotation(self, rotation):
|
|
"""
|
|
Définir la rotation par permutation.
|
|
rotation = tuple d'indices (ex: (2, 0, 1) signifie [h, l, w])
|
|
"""
|
|
self.rotation = rotation
|
|
self.dims = [self.original_dims[i] for i in rotation]
|
|
|
|
def get_all_rotations(self):
|
|
"""
|
|
Retourner les 3 rotations uniques d'une boîte (on en considère que 3 sur 6)
|
|
car les 3 autres sont des rotations de 180°
|
|
"""
|
|
l, w, h = self.original_dims
|
|
# 3 rotations principales
|
|
return [
|
|
(l, w, h), # Normal
|
|
(l, h, w), # Rotation autour axe X
|
|
(w, l, h), # Rotation autour axe Z
|
|
]
|
|
|
|
def get_coords(self):
|
|
if self.position is None:
|
|
return None
|
|
x0, y0, z0 = self.position
|
|
x1 = x0 + self.dims[0]
|
|
y1 = y0 + self.dims[1]
|
|
z1 = z0 + self.dims[2]
|
|
return (x0, y0, z0, x1, y1, z1)
|
|
|
|
|
|
class Vehicle:
|
|
def __init__(self, id, L, W, H):
|
|
self.id = id
|
|
self.dims = [L, W, H]
|
|
self.items = []
|
|
self.candidate_points = [(0, 0, 0)]
|
|
|
|
def can_place(self, item, x, y, z):
|
|
"""Vérifier si un item peut être placé à (x, y, z)"""
|
|
# 1. Vérifier les bornes du véhicule
|
|
if x + item.dims[0] > self.dims[0]: return False
|
|
if y + item.dims[1] > self.dims[1]: return False
|
|
if z + item.dims[2] > self.dims[2]: return False
|
|
|
|
# 2. Vérifier les chevauchements (Overlap)
|
|
item_x1 = x + item.dims[0]
|
|
item_y1 = y + item.dims[1]
|
|
item_z1 = z + item.dims[2]
|
|
|
|
for other in self.items:
|
|
ox0, oy0, oz0, ox1, oy1, oz1 = other.get_coords()
|
|
|
|
# Test AABB rapide
|
|
if x >= ox1 or item_x1 <= ox0: continue
|
|
if y >= oy1 or item_y1 <= oy0: continue
|
|
if z >= oz1 or item_z1 <= oz0: continue
|
|
|
|
# Collision détectée
|
|
return False
|
|
|
|
return True
|
|
|
|
def add_item(self, item, x, y, z):
|
|
"""Ajouter un item au véhicule et mettre à jour les points candidats"""
|
|
item.position = (x, y, z)
|
|
item.vehicle_id = self.id
|
|
self.items.append(item)
|
|
|
|
# Mise à jour des points candidats
|
|
x1 = x + item.dims[0]
|
|
y1 = y + item.dims[1]
|
|
z1 = z + item.dims[2]
|
|
|
|
if x1 < self.dims[0]:
|
|
self.candidate_points.append((x1, y, z))
|
|
if y1 < self.dims[1]:
|
|
self.candidate_points.append((x, y1, z))
|
|
if z1 < self.dims[2]:
|
|
self.candidate_points.append((x, y, z1))
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# ALGORITHME GLOUTON AVEC ROTATION
|
|
# ---------------------------------------------------------------------------
|
|
|
|
def solve():
|
|
"""Solveur principal avec support de rotation"""
|
|
# Lecture optimisée
|
|
input_data = sys.stdin.read().split()
|
|
if not input_data: return
|
|
iterator = iter(input_data)
|
|
|
|
try:
|
|
L = int(next(iterator))
|
|
W = int(next(iterator))
|
|
H = int(next(iterator))
|
|
M = int(next(iterator))
|
|
except StopIteration:
|
|
return
|
|
|
|
items = []
|
|
for i in range(M):
|
|
l = int(next(iterator))
|
|
w = int(next(iterator))
|
|
h = int(next(iterator))
|
|
d = int(next(iterator))
|
|
items.append(Item(i, l, w, h, d))
|
|
|
|
# --- TRI CRITIQUE POUR LA LEAGUE OR (LIFO) ---
|
|
items.sort(key=lambda x: (x.sort_d, x.volume), reverse=True)
|
|
|
|
vehicles = []
|
|
|
|
# --- PLACEMENT AVEC ROTATION ---
|
|
for item in items:
|
|
placed = False
|
|
best_vehicle = None
|
|
best_point = None
|
|
best_rotation = None
|
|
|
|
# 1. Tenter de placer dans les véhicules existants
|
|
for v in vehicles:
|
|
if placed:
|
|
break
|
|
|
|
# Trier les points candidats
|
|
v.candidate_points.sort(key=lambda p: (p[0], p[2], p[1]))
|
|
|
|
# Essayer chaque point candidat avec différentes rotations
|
|
for cx, cy, cz in v.candidate_points:
|
|
if placed:
|
|
break
|
|
|
|
# Essayer toutes les rotations
|
|
for rotation_dims in item.get_all_rotations():
|
|
# Appliquer la rotation temporaire
|
|
item.dims = list(rotation_dims)
|
|
|
|
# Vérifier si placement valide
|
|
if v.can_place(item, cx, cy, cz):
|
|
v.add_item(item, cx, cy, cz)
|
|
placed = True
|
|
break
|
|
|
|
# 2. Si non placé, créer un nouveau véhicule
|
|
if not placed:
|
|
new_v = Vehicle(len(vehicles), L, W, H)
|
|
|
|
# Essayer toutes les rotations
|
|
for rotation_dims in item.get_all_rotations():
|
|
item.dims = list(rotation_dims)
|
|
|
|
if new_v.can_place(item, 0, 0, 0):
|
|
new_v.add_item(item, 0, 0, 0)
|
|
vehicles.append(new_v)
|
|
placed = True
|
|
break
|
|
|
|
if not placed:
|
|
# Impossible même avec rotation
|
|
print("UNSAT")
|
|
return
|
|
|
|
# --- SORTIE ---
|
|
print("SAT")
|
|
|
|
# Remettre dans l'ordre initial des IDs
|
|
items.sort(key=lambda x: x.id)
|
|
|
|
for item in items:
|
|
x0, y0, z0, x1, y1, z1 = item.get_coords()
|
|
print(f"{item.vehicle_id} {x0} {y0} {z0} {x1} {y1} {z1}")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
solve()
|