Разрезы прямоугольника на детали без отходов

#include <cassert>
#include <bit>
#include <vector>
#include <unordered_map>
#include <iostream>
 
template <typename T> std::size_t hash_mix(std::size_t hash, T v)
{
  return std::rotl(hash, 1) ^ std::hash<T>()(v);
}
 
struct Rect
{ 
  unsigned dx, dy; 
 
  unsigned area() const
    { return dx * dy; }
 
  bool fits(const Rect &limits) const
    { return dx <= limits.dx && dy <= limits.dy; }
 
  struct Hash
  {
    std::size_t operator ()(const Rect &r) const
      { return hash_mix(hash_mix(0, r.dx), r.dy); }
  };
 
  friend bool operator ==(const Rect &, const Rect &) = default;    
};
 
enum class Composition
{
  ORIGINAL,
  HORIZONTAL,
  VERTICAL
};
 
struct PatternDesc
{
  unsigned waste = std::numeric_limits<unsigned>::max();
};
 
using Patterns = std::unordered_map<Rect, PatternDesc, Rect::Hash>;
 
unsigned get_total_waste(const Patterns::value_type &pattern, const Rect &limits)
{
  const Rect &box = pattern.first;
  const PatternDesc &desc = pattern.second;
  assert(box.area() <= limits.area()); 
  return limits.area() - box.area() + desc.waste;
}
 
void combine(const Patterns::value_type &a, const Patterns::value_type &b, 
             const Rect &limits,
             const Patterns &patterns, Patterns &new_patterns)
{
  const Rect &box_a = a.first, &box_b = b.first;
  const PatternDesc &desc_a = a.second, &desc_b = b.second;
 
  for (Composition composition : { Composition::HORIZONTAL, Composition::VERTICAL })
  {
    Rect box;
    if (composition == Composition::HORIZONTAL)
      box = { box_a.dx + box_b.dx, std::max(box_a.dy, box_b.dy) };
    else
      box = { std::max(box_a.dx, box_b.dx), box_a.dy + box_b.dy };
 
    assert(box_a.area() + box_b.area() <= box.area());
 
    if (!box.fits(limits))
      continue;
 
    unsigned 
      new_waste = box.area() - (box_a.area() + box_b.area()),
      waste = new_waste + desc_a.waste + desc_b.waste;
 
    Patterns::const_iterator it = patterns.find(box);
    if (it != patterns.end())
    {
      const PatternDesc &desc = it->second;
      if (waste >= desc.waste)
        continue;
    }
 
    // New or better pattern
 
    PatternDesc &new_desc = new_patterns[box];
    if (waste >= new_desc.waste)
      continue;
 
    new_desc = { waste };
  }
}
 
int main()
{
  Rect limits;
  std::cin >> limits.dx >> limits.dy;
 
  unsigned n;
  std::cin >> n;
 
  Patterns patterns, new_patterns;
 
  for (unsigned i = 0; i < n; ++i)
  {
    Rect box;
    std::cin >> box.dx >> box.dy;
    new_patterns[box] = { 0 };
    std::swap(box.dx, box.dy);
    new_patterns[box] = { 0 };
  }
 
  do
  {
    std::vector<Patterns::const_iterator> updated;
 
    while (!new_patterns.empty())
    {
      Patterns::node_type node = new_patterns.extract(new_patterns.begin());
 
      auto ir = patterns.insert(std::move(node));
      if (!ir.inserted)
      {
        assert(ir.position->first == ir.node.key());
        ir.position->second = ir.node.mapped();
      }
 
      updated.push_back(ir.position);
    }
 
    if (updated.empty())
      break;
 
    for (Patterns::const_iterator it_a : updated)
      for (const Patterns::value_type &b : patterns)
        combine(*it_a, b, limits, patterns, new_patterns);
 
  } while (true);
 
  Patterns::const_iterator it_min = patterns.begin();
  unsigned min_total_waste = get_total_waste(*it_min, limits);
 
  for (Patterns::const_iterator it = patterns.begin(); it != patterns.end(); ++it)
  {
    unsigned total_waste = get_total_waste(*it, limits);
    if (total_waste < min_total_waste)
    {
      min_total_waste = total_waste;
      it_min = it;
    }
  }
 
  std::cout << "Min waste: " << min_total_waste << std::endl;
}

#include <cassert>
#include <bit>
#include <vector>
#include <unordered_map>
#include <iostream>
#include <fstream>
 
#define DUMP_GDS
 
template <typename T> std::size_t hash_mix(std::size_t hash, T v)
{
  return std::rotl(hash, 1) ^ std::hash<T>()(v);
}
 
struct Rect
{ 
  unsigned dx, dy; 
 
  unsigned area() const
    { return dx * dy; }
 
  bool fits(const Rect &limits) const
    { return dx <= limits.dx && dy <= limits.dy; }
 
  struct Hash
  {
    std::size_t operator ()(const Rect &r) const
      { return hash_mix(hash_mix(0, r.dx), r.dy); }
  };
 
  friend bool operator ==(const Rect &, const Rect &) = default;    
};
 
enum class Composition
{
  ORIGINAL,
  HORIZONTAL,
  VERTICAL
};
 
struct PatternDesc
{
  unsigned waste = std::numeric_limits<unsigned>::max();
 
#ifdef DUMP_GDS
  unsigned id;
  Composition composition = Composition::ORIGINAL;
  Rect key_a, key_b; // Patterns::const_iterator it_a, it_b;
  mutable bool is_dumped = false;
#endif // DUMP_GDS
};
 
using Patterns = std::unordered_map<Rect, PatternDesc, Rect::Hash>;
 
unsigned get_total_waste(const Patterns::value_type &pattern, const Rect &limits)
{
  const Rect &box = pattern.first;
  const PatternDesc &desc = pattern.second;
  assert(box.area() <= limits.area()); 
  return limits.area() - box.area() + desc.waste;
}
 
void combine(const Patterns::value_type &a, const Patterns::value_type &b, 
             const Rect &limits,
             const Patterns &patterns, Patterns &new_patterns)
{
  const Rect &box_a = a.first, &box_b = b.first;
  const PatternDesc &desc_a = a.second, &desc_b = b.second;
 
  for (Composition composition : { Composition::HORIZONTAL, Composition::VERTICAL })
  {
    Rect box;
    if (composition == Composition::HORIZONTAL)
      box = { box_a.dx + box_b.dx, std::max(box_a.dy, box_b.dy) };
    else
      box = { std::max(box_a.dx, box_b.dx), box_a.dy + box_b.dy };
 
    assert(box_a.area() + box_b.area() <= box.area());
 
    if (!box.fits(limits))
      continue;
 
    unsigned 
      new_waste = box.area() - (box_a.area() + box_b.area()),
      waste = new_waste + desc_a.waste + desc_b.waste;
 
    Patterns::const_iterator it = patterns.find(box);
    if (it != patterns.end())
    {
      const PatternDesc &desc = it->second;
      if (waste >= desc.waste)
        continue;
    }
 
    // New or better pattern
 
    PatternDesc &new_desc = new_patterns[box];
    if (waste >= new_desc.waste)
      continue;
 
    new_desc = { waste };
 
#ifdef DUMP_GDS
    static unsigned i_desc_id;
    new_desc.id = ++i_desc_id; 
    new_desc.composition = composition;
    new_desc.key_a = box_a;
    new_desc.key_b = box_b;
#endif // DUMP_GDS
  }
}
 
#ifdef DUMP_GDS
 
void dump_gds_sname(std::ofstream &f, Patterns::const_iterator it_cell)
{
  const Rect &box = it_cell->first;
  const PatternDesc &desc = it_cell->second;
  f << (desc.composition == Composition::ORIGINAL ? "Box_" : "Pattern_") << 
    desc.id << "_" << box.dx << "x" << box.dy;
}
 
void dump_gds_rect(std::ofstream &f, unsigned layer, const Rect &r)
{
  f << "BOUNDARY" << std::endl;
  f << "LAYER " << layer << std::endl;
  f << "DATATYPE 0" << std::endl;
  f << "XY 0:0" << std::endl;
  f << r.dx << ":0" << std::endl;
  f << r.dx << ":" << r.dy << std::endl;
  f << "0:" << r.dy << std::endl;
  f << "0:0" << std::endl;
  f << "ENDEL" << std::endl;
}
 
void dump_gds_cell(std::ofstream &f, Patterns::const_iterator it_cell, const Patterns &patterns)
{
  const Rect &box = it_cell->first;
  const PatternDesc &desc = it_cell->second;
 
  if (desc.is_dumped)
    return;
 
  desc.is_dumped = true;
 
  f << "BGNSTR 1/1/2022 00:00:00 1/1/2022 00:00:00" << std::endl;
  f << "STRNAME "; dump_gds_sname(f, it_cell); f << std::endl;
 
  Patterns::const_iterator it_sub_cell_a, it_sub_cell_b;
 
  if (desc.composition == Composition::ORIGINAL)
    dump_gds_rect(f, desc.id, box);
  else
  {
    it_sub_cell_a = patterns.find(desc.key_a);
    it_sub_cell_b = patterns.find(desc.key_b);
    assert(it_sub_cell_a != patterns.end() && it_sub_cell_b != patterns.end());
 
    f << "SREF" << std::endl;
    f << "SNAME "; dump_gds_sname(f, it_sub_cell_a); f << std::endl;
    f << "XY 0:0" << std::endl;
    f << "ENDEL" << std::endl;
 
    f << "SREF" << std::endl;
    f << "SNAME "; dump_gds_sname(f, it_sub_cell_b); f << std::endl;
 
    if (desc.composition == Composition::HORIZONTAL)
      f << "XY " << it_sub_cell_a->first.dx << ":0" << std::endl;
    else
      f << "XY 0:" << it_sub_cell_a->first.dy << std::endl;
 
    f << "ENDEL" << std::endl;
  }
 
  f << "ENDSTR" << std::endl << std::endl;
 
  if (desc.composition != Composition::ORIGINAL)
  {
    dump_gds_cell(f, it_sub_cell_a, patterns);
    dump_gds_cell(f, it_sub_cell_b, patterns);
  }
}
 
void dump_gds(const char *file, Patterns::const_iterator it_root, 
              const Patterns &patterns, const Rect &limits )
{
  std::ofstream f(file);
  if (!f)
    return;
 
  f << "HEADER 600" << std::endl;
  f << "BGNLIB 1/1/2022 00:00:00 1/1/2022 00:00:00" << std::endl;
  f << "LIBNAME " << limits.dx << "x" << limits.dy << std::endl;
  f << "UNITS 0.001 1e-09" << std::endl << std::endl;
 
  f << "BGNSTR 1/1/2022 00:00:00 1/1/2022 00:00:00" << std::endl;
  f << "STRNAME Result_" << limits.dx << "x" << limits.dy << std::endl;
  dump_gds_rect(f, 0, limits);
  f << "SREF" << std::endl;
  f << "SNAME "; dump_gds_sname(f, it_root); f << std::endl;
  f << "XY 0:0" << std::endl;
  f << "ENDEL" << std::endl;
  f << "ENDSTR" << std::endl << std::endl;
 
  dump_gds_cell(f, it_root, patterns);
 
  f << "ENDLIB" << std::endl;
}
 
#endif // DUMP_GDS
 
int main()
{
  Rect limits;
  std::cin >> limits.dx >> limits.dy;
 
  unsigned n;
  std::cin >> n;
 
  Patterns patterns, new_patterns;
 
  for (unsigned i = 0; i < n; ++i)
  {
    Rect box;
    std::cin >> box.dx >> box.dy;
 
    {
      PatternDesc &desc = new_patterns[box];
      desc = { 0 };
#ifdef DUMP_GDS
      desc.id = i + 1;
      desc.composition = Composition::ORIGINAL;
#endif // DUMP_GDS
    }
      
    std::swap(box.dx, box.dy);
 
    {
      PatternDesc &desc = new_patterns[box];
      desc = { 0 };
#ifdef DUMP_GDS
      desc.id = i + 1;
      desc.composition = Composition::ORIGINAL;
#endif // DUMP_GDS
    }
  }
 
  do
  {
    std::vector<Patterns::const_iterator> updated;
 
    while (!new_patterns.empty())
    {
      Patterns::node_type node = new_patterns.extract(new_patterns.begin());
 
      auto ir = patterns.insert(std::move(node));
      if (!ir.inserted)
      {
        assert(ir.position->first == ir.node.key());
        ir.position->second = ir.node.mapped();
      }
 
      updated.push_back(ir.position);
    }
 
    if (updated.empty())
      break;
 
    for (Patterns::const_iterator it_a : updated)
      for (const Patterns::value_type &b : patterns)
        combine(*it_a, b, limits, patterns, new_patterns);
 
  } while (true);
 
  Patterns::const_iterator it_min = patterns.begin();
  unsigned min_total_waste = get_total_waste(*it_min, limits);
 
  for (Patterns::const_iterator it = patterns.begin(); it != patterns.end(); ++it)
  {
    unsigned total_waste = get_total_waste(*it, limits);
    if (total_waste < min_total_waste)
    {
      min_total_waste = total_waste;
      it_min = it;
    }
  }
 
  std::cout << "Min waste: " << min_total_waste << std::endl;
 
#ifdef DUMP_GDS
  std::cout << "Saving GDS file..." << std::endl;
  dump_gds("result.gds", it_min, patterns, limits);
  std::cout << "Done." << std::endl;
#endif // DUMP_GDS
}