2014
02-23

# Zigzag

Given several points on a plane, let’s try to solve a puzzle connecting them with a zigzag line.

The puzzle is to find the zigzag line that passes through all the given points with the minimum number of turns. Moreover, when there are several zigzag lines with the minimum number of turns, the shortest one among them should be found.

For example, consider nine points given in Figure 10.
A zigzag line is composed of several straight line segments. Here, the rule requests that each line segment should pass through two or more given points.

A zigzag line may turn at some of the given points or anywhere else. There may be some given points passed more than once.

Two zigzag lines with three turning points are depicted in Figure 11 (a) and (b) for the same set of given points shown in Figure 10. The length of the zigzag line in Figure 11 (a) is shorter than that in Figure 11 (b). In fact, the length of the zigzag line in Figure 11 (a) is shortest so that it is the solution for the nine points given in Figure 10.

Another zigzag line with four turning points is depicted in Figure 12. Its length is shorter than those in Figure 11, however, the number of turning points is greater than those in Figure 11, and thus, it is not the solution.

There are two zigzag lines that passes another set of given points depicted in Figure 13 (a) and (b).

Both have the same number of turning points, and the line in (a) is longer than that in (b). However, the solution is (a), because one of the segments of the zigzag line in (b) passes only one given point, violating the rule.

Your job is to write a program that solves this puzzle.

The input consists of multiple datasets, followed by a line containing one zero. Each dataset has the following format.
n

x1 y1

xn yn

Every input item in a dataset is a non-negative integer. Items in a line are separated by a single space. n is the number of the given points. xk and yk (k = 1,…. n) indicate the position of the k-th point. The order of the points is meaningless. You can assume that 2 ≤ n ≤ 10, 0 ≤ xk ≤ 10, and 0 ≤ yk ≤ 10.

The input consists of multiple datasets, followed by a line containing one zero. Each dataset has the following format.
n

x1 y1

xn yn

Every input item in a dataset is a non-negative integer. Items in a line are separated by a single space. n is the number of the given points. xk and yk (k = 1,…. n) indicate the position of the k-th point. The order of the points is meaningless. You can assume that 2 ≤ n ≤ 10, 0 ≤ xk ≤ 10, and 0 ≤ yk ≤ 10.

2
0 0
10 9
4
0 0
3 1
0 3
3 3
10
2 2
4 2
6 2
2 4
4 4
6 4
2 6
4 6
6 6
3 3
10
0 0
2 0
4 0
0 2
2 2
4 2
0 4
2 4
4 4
6 8
9
0 0
1 0
3 0
0 1
1 1
3 1
0 2
1 2
2 2
10
0 0
1 0
0 1
1 1
9 9
9 10
10 9
10 10
0 2
10 8
10
0 0
0 10
2 0
2 1
2 7
2 10
5 1
6 7
9 2
10 9
0

0 13.45362405
1 18.48683298
3 24.14213562
4 24.94813673
3 12.24264069
3 60.78289622
3 502.7804353

Hint

Figure 14: Example solutions for the first and the second datasets in the sample inputs.

Figure 15: Example solutions for the third and the fourth datasets in the
sample inputs.


AC代码：

/*
* Author: OpenLegend
* Created Time:  2010-8-27 15:42:05
* File Name: J.cpp
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;

const double eps = 1e-8;
const double pi = acos(-1.0);

int sgn(double d) {
if (d > eps)
return 1;
if (d < -eps)
return -1;
return 0;
}

struct point {
double x, y;
point(double _x = 0, double _y = 0): x(_x), y(_y) {
}
void input() {
scanf("%lf%lf", &x, &y);
}
double len() const {
return sqrt(x * x + y * y);
}
point trunc(double l) const {
double r = l / len();
return point(x * r, y * r);
}
point rotate_left() const {
return point(-y, x);
}
point rotate_right() const {
return point(y, -x);
}
};

bool operator==(const point& p1, const point& p2) {
return sgn(p1.x - p2.x) == 0 && sgn(p1.y - p2.y) == 0;
}

bool operator<(const point& p1, const point& p2) {
return sgn(p1.x - p2.x) == 0 ? sgn(p1.y - p2.y) < 0 : p1.x < p2.x;
}

point operator+(const point& p1, const point& p2) {
return point(p1.x + p2.x, p1.y + p2.y);
}

point operator-(const point& p1, const point& p2) {
return point(p1.x - p2.x, p1.y - p2.y);
}

double operator^(const point& p1, const point& p2) {
return p1.x * p2.x + p1.y * p2.y;
}

double operator*(const point& p1, const point& p2) {
return p1.x * p2.y - p1.y * p2.x;
}

bool get_intersection(const point& p1, const point& p2, const point& p3, const point& p4, point& c) {
double d1 = (p2 - p1) * (p3 - p1), d2 = (p2 - p1) * (p4 - p1);
if (sgn(d1 - d2) == 0)
return false;
c = point((p3.x * d2 - p4.x * d1) / (d2 - d1), (p3.y * d2 - p4.y * d1) / (d2 - d1));
return true;
}

int n;
point p[16];
pair<int, double> dp[1 << 11][11][11], ans;

bool solve();
void compute();

int main() {
while (solve());
return 0;
}

bool solve() {
scanf("%d", &n);
if (n == 0)
return false;
for (int i = 0; i < n; ++i)
p[i].input();
sort(p, p + n);
n = unique(p, p + n) - p;
if (n < 2) {
puts("0 0.0000000");
return true;
}
compute();
printf("%d %.8lf\n", ans.first, ans.second);
return true;
}

void compute() {
for (int i = 0; i < (1 << n); ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k)
dp[i][j][k].first = 256;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j)
continue;
dp[(1 << i) | (1 << j)][i][j] = make_pair(0, (p[j] - p[i]).len());
}
}
for (int i = 0; i < (1 << n); ++i) {
for (int x = 0; x < n; ++x) {
if (((i >> x) & 1) == 0)
continue;
for (int y = 0; y < n; ++y) {
if (y == x || ((i >> y) & 1) == 0)
continue;
if (dp[i][x][y].first == 256)
continue;
pair<int, double>& cur = dp[i][x][y];
for (int j = 0; j < n; ++j) {
if (((i >> j) & 1) == 1)
continue;
pair<int, double>& res = dp[i | (1 << j)][y][j];
if (sgn((p[j] - p[x]) * (p[y] - p[x])) == 0) {
if (sgn((p[j] - p[y]) ^ (p[x] - p[y])) < 0) {
res = min(res, make_pair(cur.first, cur.second + (p[j] - p[y]).len()));
} else {
res = min(res, make_pair(cur.first + 1, cur.second + (p[j] - p[y]).len()));
}
} else {
res = min(res, make_pair(cur.first + 1, cur.second + (p[j] - p[y]).len()));
}
}
for (int j = 0; j < n; ++j) {
if (((i >> j) & 1) == 1)
continue;
for (int k = 0; k < n; ++k) {
if (k == j || ((i >> k) & 1) == 1)
continue;
pair<int, double>& res = dp[i | (1 << j) | (1 << k)][j][k];
point c;
if (get_intersection(p[x], p[y], p[j], p[k], c)) {
if (sgn((p[x] - p[y]) ^ (c - p[y])) < 0 && sgn((p[k] - p[j]) ^ (c - p[j])) < 0) {
res = min(res, make_pair(cur.first + 1, cur.second + (c - p[y]).len() + (c - p[k]).len()));
}
}
}
}
}
}
}
ans.first = 256;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
ans = min(ans, dp[(1 << n) - 1][i][j]);
}

1. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。