Metal Cutting

In order to build a ship to travel to Eindhoven, The Netherlands, various sheet metal parts have to be cut from rectangular pieces of sheet metal. Each part is a convex polygon with at most 8 vertices. Each rectangular piece of sheet metal has width n and height m, so that the four corners of the sheet can be specified by the Cartesian coordinates (0, 0), (0, m), (n, m) and (n, 0) in clockwise order. The cutting machine available can make only straight-line cuts completely through the metal. That is, it cannot cut halfway through the sheet, turn, and then cut some more. You are asked to write a program to determine the minimum total length of cuts this machine has to make in order to cut out the polygon. The cuts must be along the edges of the poligon.

For example, if n = m = 100, and the polygon has vertices (80, 80), (70, 30), (20, 20) and (20, 80), the following diagram shows the optimal cut (the thick lines). The numbers show the order in which the cuts are made.

<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPGgyPklucHV0IDwvaDI+ClRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBhbiBpbnRlZ2VyIE4sIHRoZW4gYSBibGFuayBsaW5lIGZvbGxvd2VkIGJ5IE4gZGF0YXNldHMuIFRoZXJlIGlzIGEgYmxhbmsgbGluZSBiZXR3ZWVuIGRhdGFzZXRzLgo8cD5UaGUgZmlyc3QgbGluZSBvZiBlYWNoIGRhdGFzZXQgY29udGFpbnMgdGhlIHR3byBpbnRlZ2VycyA8ZW0+bjwvZW0+IGFuZCA8ZW0+bTwvZW0+IHdoZXJlIDxpbWcgd2lkdGg9"119" height="30" align="MIDDLE" border="0" src="http://www.2cto.com/uploadfile/Collfiles/20140313/20140313084921198.gif" alt="$0 < n, m \le 500$">. The next line contains p, the number of vertices in the polygon, where . Each of the next p lines contains two integers x and y where 0 < x < n and 0 < y < m, specifying the vertices of the polygon. The vertices are listed in clockwise order. You may assume that the polygon does not intersect itself, and that no three consecutive vertices are colinear.

Output

For each dataset, print the minimum total length of cuts required to cut out the given polygon, accurate to 3 decimal places. Print a blank line between datasets.

Sample Input

1

100 100
4
80 80
70 30
20 20
20 80

Sample Output

Minimum total length = 312.575

題意：一個矩形上面有n個點，組成n條直線，現在求一個切割順序，使得切割長度最小。

思路：最多8條直線，直接暴力切割順序，然後去求，求的過程中，每切一條直線就添加進去，然後求長度的時候遍歷一遍現有直線，然後就是幾何問題了。

利用叉積判斷點是否是可取點，然後在這些點找最小距離的點，這樣可以求出兩個交點，即求出長度。

代碼：

#include 
#include 
#include 
#include 
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
const double esp = 1e-9;
using namespace std;
struct Point {
	double x, y;
	Point() {}
	Point(double xx, double yy) {
		x = xx; y = yy;
	}
} p[10];

struct Line {
	Point a, b;
	double A, B, C;
	Line() {}
	Line(Point aa, Point bb) {
		a = aa; b = bb;
		A = b.y - a.y;
		B = a.x - b.x;
		C = (A * a.x + B * a.y);
	}
} l[15], save[15];

inline bool px(Line a, Line b) {
	if (fabs((a.b.y - a.a.y) * (b.b.x - b.a.x) - (b.b.y - b.a.y) * (a.b.x - a.a.x)) < esp) return true;
	return false;
}

inline Point jd(Line a, Line b) {
	Point pp((b.B * a.C - a.B * b.C) / (a.A * b.B - b.A * a.B) ,(a.A * b.C - b.A * a.C) / (a.A * b.B - b.A * a.B));
	return pp;
}

int t, P, ln, sn, i, ord[10];
double n, m;

inline double dis(Point a, Point b) {
	return sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}

inline bool outside(Point a, Point b, Point c) {
	return (c.x - a.x) * (b.x - a.x) + (c.y - a.y) * (b.y - a.y) > esp;
}

inline double find(Line li) {
	double mina = 2000000000, minb = 2000000000;
	Point aa, bb;
	for (int i = 0; i < sn; i++) {
		if (px(li, save[i])) continue;
		Point c = jd(li, save[i]);
		double disa = dis(li.a ,c), disb = dis(li.b , c);
		if (outside(li.b, li.a, c) && disa - mina < esp) {
			mina = disa;
			aa = c;
		}
		if (outside(li.a, li.b, c) && disb - minb < esp) {
			minb = disb;
			bb = c;
		}
	}
	return dis(aa, bb);
}

inline double cal() {
	double sum = 0;
	sn = 4;
	for (int i = 0; i < P; i++) {
		sum += find(l[ord[i]]);
		save[sn++] = l[ord[i]];
	}
	return sum;
}

inline double solve() {
	double ans = 2000000000;
	save[sn++] = Line(Point(0, 0), Point(0, m));
	save[sn++] = Line(Point(0, 0), Point(n, 0));
	save[sn++] = Line(Point(n, 0), Point(n, m));
	save[sn++] = Line(Point(0, m), Point(n, m));
	do {
		double t = cal();
		ans = min(ans, t);
	} while (next_permutation(ord, ord + P));
	return ans;
}

int main() {
	scanf("%d", &t);
	while (t--) {
		ln = 0, sn = 0;
		scanf("%lf%lf", &n, &m);
		scanf("%d", &P);
		for (i = 0; i < P; i++) {
			ord[i] = i;
			scanf("%lf%lf", &p[i].x, &p[i].y);
			if (i != 0)
				l[ln++] = Line(Point(p[i - 1].x, p[i - 1].y), Point(p[i].x, p[i].y));
		}
		l[ln++] = Line(Point(p[P - 1].x, p[P - 1].y), Point(p[0].x, p[0].y));
		printf("Minimum total length = %.3lf\n", solve());
		if (t) printf("\n");
	}
	return 0;
}