POJ 1514 - Metal Cutting

http://poj.org/problem?id=1514

概要

(0,0), (0,m), (n,m), (n,0) という座標を頂点とした n * m の鉄板がある． これを cutting machine で切って，与えられた座標を頂点とする凸な p 角形を切り出したい．

cutting machine は多角形の端から端までしか切ることができない． つまり，鉄板の途中まで切って向きを変えるというような操作はできない．

切った長さを最小にしたい．そのときの長さを答える．

制約

解法

全探索 + 多角形の切断で O(p! * p * p)．

切断するときに交点を覚えておいて，切った長さも返すように実装した．

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <complex>
  4 using namespace std;
  5 typedef complex<double> P;
  6 static const double EPS = 1e-6;
  7 
  8 inline double cross(const P& a, const P& b)
  9 {
 10   return a.real()*b.imag() - b.real()*a.imag();
 11 }
 12 
 13 struct line
 14 {
 15   P a, b;
 16   line() {}
 17   line(const P& x, const P& y) : a(x), b(y) {}
 18 
 19   inline bool parallel(const line& ln) const
 20   {
 21     return abs(cross(ln.b - ln.a, b - a)) < EPS;
 22   }
 23 
 24   inline bool intersects(const line& ln) const
 25   {
 26     return !parallel(ln);
 27   }
 28 
 29   inline P intersection(const line& ln) const
 30   {
 31     const P x = b - a;
 32     const P y = ln.b - ln.a;
 33     return a + x*(cross(y, ln.a - a))/cross(y, x);
 34   }
 35 };
 36 
 37 struct segment
 38 {
 39   P a, b;
 40   segment() {}
 41   segment(const P& x, const P& y) : a(x), b(y) {}
 42 
 43   inline bool intersects(const line& ln) const
 44   {
 45     return cross(ln.b - ln.a, a - ln.a) * cross(ln.b - ln.a, b - ln.a) < EPS;
 46   }
 47 
 48   inline P intersection(const line& ln) const
 49   {
 50     const P x = b - a;
 51     const P y = ln.b - ln.a;
 52     return a + x*(cross(y, ln.a - a))/cross(y, x);
 53   }
 54 
 55   inline bool parallel(const line& ln) const
 56   {
 57     return abs(cross(ln.b - ln.a, b - a)) < EPS;
 58   }
 59 };
 60 
 61 struct polygon
 62 {
 63   P ps[16];
 64   int N;
 65   polygon() : N(0) {}
 66 
 67   inline int size() const { return N; }
 68   inline void push_back(const P& p) { ps[N++] = p; }
 69   inline P& operator[](int i) { return ps[i]; }
 70   inline const P& operator[](int i) const { return ps[i]; }
 71 
 72   pair<polygon,double> cut(const line& ln) const
 73   {
 74     // cut out the left-side of the line
 75     polygon ret;
 76     P crosspoint[2];
 77     int cp = 0;
 78     for (int i = 0; i < N; i++) {
 79       const segment seg(ps[i], ps[(i+1)%N]);
 80       if (cross(ln.b - ln.a, ps[i] - ln.a) < EPS) {
 81         // ps[i] is right-side of the line
 82         ret.push_back(ps[i]);
 83         if (!seg.parallel(ln) && seg.intersects(ln)) {
 84           const P p = seg.intersection(ln);
 85           if (abs(p - ps[i]) > EPS) {
 86             ret.push_back(p);
 87             crosspoint[cp++] = p;
 88           }
 89         }
 90       } else if (!seg.parallel(ln) && seg.intersects(ln)) {
 91         const P p = seg.intersection(ln);
 92         ret.push_back(p);
 93         crosspoint[cp++] = p;
 94       }
 95     }
 96     if (cp == 2) {
 97       return make_pair(ret, abs(crosspoint[1] - crosspoint[0]));
 98     } else {
 99       throw "???";
100     }
101   }
102 };
103 
104 int main()
105 {
106   int n, m;
107   scanf("%d %d", &n, &m);
108   int p;
109   scanf("%d", &p);
110   P ps[8];
111   for (int i = 0; i < p; i++) {
112     int x, y;
113     scanf("%d %d", &x, &y);
114     ps[i] = P(x, y);
115   }
116   line ls[8];
117   int a[8];
118   for (int i = 0; i < p; i++) {
119     ls[i] = line(ps[i], ps[(i+1)%p]);
120     a[i] = i;
121   }
122 
123   double ans = 1e9;
124   do {
125     polygon poly;
126     poly.push_back(P(0, 0));
127     poly.push_back(P(0, m));
128     poly.push_back(P(n, m));
129     poly.push_back(P(n, 0));
130     double len = 0.0;
131     for (int i = 0; i < p; i++) {
132       const pair<polygon,double> r = poly.cut(ls[a[i]]);
133       len += r.second;
134       poly = r.first;
135     }
136     ans = min(ans, len);
137   } while (next_permutation(a, a+p));
138   printf("Minimum total length = %.3f\n", ans);
139   return 0;
140 }
poj/1514.cc