poj 1514 Metal Cutting (dfs+多边形切割)

　　一道类似于半平面交的题。

　　题意相当简单，给出一块矩形以及最后被切出来的的多边形各个顶点的位置。每次切割必须从一端切到另一端，问切出多边形最少要切多长的距离。

　　因为最短的切割距离肯定是没有多余的切割痕迹的，而且对于多边形的每一条边，都需要至少经过一次，也就是这些是必要切割。又因为最多就只有8条切割的痕迹，所以我们可以枚举每条痕迹的先后次序，然后模拟切割即刻。复杂度O(n!*n)。

代码如下：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <vector>
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 using namespace std;
  9 
 10 const double EPS = 1e-8;
 11 const double PI = acos(-1.0);
 12 template <class T> T sqr(T x) { return x * x;}
 13 struct Point {
 14     double x, y;
 15     Point() {}
 16     Point(double x, double y) : x(x), y(y) {}
 17 } ;
 18 typedef Point Vec;
 19 Vec operator + (Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y);}
 20 Vec operator - (Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y);}
 21 Vec operator * (Vec a, double p) { return Vec(a.x * p, a.y * p);}
 22 Vec operator / (Vec a, double p) { return Vec(a.x / p, a.y / p);}
 23 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
 24 bool operator < (Point a, Point b) { return sgn(a.x - b.x) < 0 || sgn(a.x - b.x) == 0 && a.y < b.y;}
 25 bool operator == (Point a, Point b) { return sgn(a.x - b.x) == 0 && sgn(a.y - b.y) == 0;}
 26 
 27 inline double dotDet(Vec a, Vec b) { return a.x * b.x + a.y * b.y;}
 28 inline double crossDet(Vec a, Vec b) { return a.x * b.y - a.y * b.x;}
 29 inline double dotDet(Point o, Point a, Point b) { return dotDet(a - o, b - o);}
 30 inline double crossDet(Point o, Point a, Point b) { return crossDet(a - o, b - o);}
 31 inline double vecLen(Vec x) { return sqrt(dotDet(x, x));}
 32 inline Vec vecUnit(Vec x) { return x / vecLen(x);}
 33 inline Vec normal(Vec x) { return Vec(-x.y, x.x) / vecLen(x);}
 34 inline bool onSeg(Point x, Point a, Point b) { return sgn(crossDet(x, a, b)) == 0 && sgn(dotDet(x, a, b)) < 0;}
 35 
 36 int segIntersect(Point a, Point c, Point b, Point d) {
 37     Vec v1 = b - a, v2 = c - b, v3 = d - c, v4 = a - d;
 38     int a_bc = sgn(crossDet(v1, v2));
 39     int b_cd = sgn(crossDet(v2, v3));
 40     int c_da = sgn(crossDet(v3, v4));
 41     int d_ab = sgn(crossDet(v4, v1));
 42 //    cout << a_bc << ' ' << b_cd << ' ' << c_da << ' ' << d_ab << endl;
 43     if (a_bc * c_da > 0 && b_cd * d_ab > 0) return 1;
 44     if (onSeg(b, a, c) && c_da) return 2;
 45     if (onSeg(c, b, d) && d_ab) return 2;
 46     if (onSeg(d, c, a) && a_bc) return 2;
 47     if (onSeg(a, d, b) && b_cd) return 2;
 48     return 0;
 49 }
 50 
 51 Point lineIntersect(Point P, Vec v, Point Q, Vec w) {
 52     Vec u = P - Q;
 53     double t = crossDet(w, u) / crossDet(v, w);
 54     return P + v * t;
 55 }
 56 
 57 struct Poly {
 58     vector<Point> pt;
 59     Poly() { pt.clear();}
 60     ~Poly() {}
 61     Poly(vector<Point> &pt) : pt(pt) {}
 62     Point operator [] (int x) const { return pt[x];}
 63     int size() { return pt.size();}
 64 } ;
 65 
 66 Poly cutPoly(Poly &poly, Point a, Point b) {
 67     Poly ret = Poly();
 68     int n = poly.size();
 69     for (int i = 0; i < n; i++) {
 70         Point c = poly[i], d = poly[(i + 1) % n];
 71         if (sgn(crossDet(a, b, c)) >= 0) ret.pt.push_back(c);
 72         if (sgn(crossDet(b - a, c - d)) != 0) {
 73             Point ip = lineIntersect(a, b - a, c, d - c);
 74             if (onSeg(ip, c, d)) ret.pt.push_back(ip);
 75         }
 76     }
 77     return ret;
 78 }
 79 
 80 const double dir[4][2] = { {0.0, 0.0}, {1.0, 0.0}, {1.0, 1.0}, {0.0, 1.0}};
 81 const double FINF = 1e100;
 82 bool vis[10];
 83 Point rec[10];
 84 double minLen;
 85 
 86 void dfs(int p, int n, Poly &poly, double len) {
 87 //    for (int i = 0; i < n; i++) cout << vis[i]; cout << endl;
 88     if (p >= n) {
 89         minLen = min(len, minLen);
 90         return ;
 91     }
 92     for (int i = 0; i < n; i++) {
 93 //        cout << i << endl;
 94         if (vis[i]) continue;
 95         vis[i] = true;
 96         Vec d = vecUnit(rec[(i + 1) % n] - rec[i]) * 500.0;
 97 //        cout << rec[(i + 1) % n].x << ' ' << rec[(i + 1) % n].y << " !!! " << rec[i].x << ' ' << rec[i].y << endl;
 98 //        cout << d.x << ' ' << d.y << endl;
 99         Point s = rec[(i + 1) % n] + d, t = rec[i] - d;
100         vector<Point> ip;
101         ip.clear();
102         for (int j = 0, sz = poly.size(); j < sz; j++) {
103             if (segIntersect(s, t, poly[j], poly[(j + 1) % sz])) {
104                 ip.push_back(lineIntersect(s, t - s, poly[j], poly[(j + 1) % sz] - poly[j]));
105 //                cout << "has one" << endl;
106             }
107         }
108         sort(ip.begin(), ip.end());
109         int cnt = (int) (unique(ip.begin(), ip.end()) - ip.begin());
110         if (cnt != 2) {
111             puts("shit!!");
112             while (1) {}
113         }
114         Poly tmp = cutPoly(poly, s, t);
115         dfs(p + 1, n, tmp, len + vecLen(ip[0] - ip[1]));
116         vis[i] = false;
117     }
118 }
119 
120 int main() {
121 //    freopen("in", "r", stdin);
122     double x, y;
123     int n;
124     while (cin >> x >> y) {
125         Poly tmp = Poly();
126         for (int i = 0; i < 4; i++) tmp.pt.push_back(Point(dir[i][0] * x, dir[i][1] * y));
127         memset(vis, false, sizeof(vis));
128         cin >> n;
129         for (int i = 0; i < n; i++) cin >> rec[i].x >> rec[i].y;
130         minLen = FINF;
131         dfs(0, n, tmp, 0.0);
132         printf("Minimum total length = %.3f
", minLen);
133     }
134     return 0;
135 }

View Code

——written by Lyon