1294-Zigzag

問題概要

いくつかの点が与えられる．
その点を全て通るような折れ線を求めよ．
ただし，折れ曲る回数が出来るだけ少なく，かつ長さの合計が出来るだけ少なくなるようにせよ．
また折れ線に含まれる各線分はかならず与えられた点を2つより多く通らないといけないものとする．

解法

2つの点を通る全ての直線をリストアップし，その任意の2つの交点を全て求める．
後は点について最良優先探索(ダイクストラ)する．

実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <complex>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <queue>
#include <cstdlib>
using namespace std;

typedef long long int lli;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define rep(i,s,x) for(int i=s;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
const double EPS=1e-4;
typedef complex<double> Point;
inline double size(const Point &a){return abs(a);}
inline double cross(const Point &a,const Point &b){return imag(conj(a)*b);}
inline double dot(const Point &a,const Point &b){return real(conj(a)*b);}
inline double atan(const Point &a){return atan2(imag(a),real(a));}

namespace std{
bool operator<(const Point &a,const Point &b){return real(a)==real(b)?imag(a)<imag(b):real(a)<real(b);}
Point operator*(const Point &a,const double &b){return Point(real(a)*b,imag(a)*b);}
}
struct Line:vector<Point>{
	Line(Point a,Point b){
		(*this).push_back(a);(*this).push_back(b);
	}
};
int ccw(Point a,Point b,Point c){
	b-=a;c-=a;
	if(cross(b, c)>0)return +1;       // counter clockwise
	if(cross(b, c)<0)return -1;       // clockwise
	if(dot(b, c)<0)return +2;       // c--a--b on line
	if(norm(b)<norm(c))return -2;       // a--b--c on line
	return 0;
}
bool is_intersect_LL(const Line &l, const Line &m) {
	return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || // non-parallel
			abs(cross(l[1]-l[0], m[0]-l[0])) < EPS;   // same line
}
bool is_intersect_SP(const Line &s, const Point &p) {
	return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < 1e-8; // triangle inequality
}
Point crosspoint_LL(const Line &l, const Line &m) {
	double A = cross(l[1] - l[0], m[1] - m[0]);
	double B = cross(l[1] - l[0], l[1] - m[0]);
	if (abs(A) < EPS && abs(B) < EPS) return m[0]; // same line
	return m[0] + B / A * (m[1] - m[0]);
}
ostream &operator<<(ostream &os,const Point &a){
	os<<"("<<real(a)<<","<<imag(a)<<")";
	return os;
}
int n;
vector<Point> points;
vector<Point> pts;
struct State{
	int count;
	double ans;
	int used;
	int now;
};
bool operator<(const State &a,const State &b){
	return a.count!=b.count?a.count<b.count:a.ans<b.ans;
}
bool operator>(const State &b,const State &a){return a<b;}
#define MAXpts 1200
int data[MAXpts][MAXpts];
char ac[6][1<<10][MAXpts];
vector<int> next[MAXpts];
void solve(){
	priority_queue<State,vector<State>,greater<State> > que;
	REP(i,n)que.push((State){-1,0,0,i});
	memset(ac,0,sizeof(ac));
	while(!que.empty()){
		State now=que.top();que.pop();
		if(ac[now.count+1][now.used][now.now])continue;
		ac[now.count+1][now.used][now.now]=1;
		if(now.used==(1<<n)-1){
			cout<<now.count<<" "<<setprecision(5)<<setiosflags(ios::fixed)<<now.ans<<endl;
			return;
		}
		if(now.count==4)continue;
		REP(i,next[now.now].size()){
			//次の場所を探す
			if((now.used|data[now.now][next[now.now][i]])!=now.used){
				que.push((State){now.count+1,now.ans+abs(pts[now.now]-pts[next[now.now][i]]),now.used|data[now.now][next[now.now][i]],next[now.now][i]});
			}
		}
	}
	cerr<<"No Answer Error"<<endl;
}
int main(){
	for(;cin>>n,n;){
		points=vector<Point>(n);
		REP(i,n){
			int x,y;
			cin>>x>>y;
			points[i].real()=x;
			points[i].imag()=y;
		}
		vector<Line> lines;
		REP(i,n){
			rep(j,i+1,n){
				lines.push_back(Line(points[i],points[j]));
			}
		}
		pts.clear();
		REP(i,n){
			pts.push_back(points[i]);
		}
		REP(i,lines.size()){
			rep(j,i+1,lines.size()){
				if(is_intersect_LL(lines[i],lines[j])){
					Point ne=crosspoint_LL(lines[i],lines[j]);
					bool ok=true;
					REP(k,pts.size()){
						if(pts[k]==ne)ok=false;
					}
					if(ok)pts.push_back(ne);
				}
			}
		}
		REP(i,pts.size()){
			rep(j,i,pts.size()){
				data[i][j]=0;
				Line t=Line(pts[i],pts[j]);
				REP(k,n){
					if(is_intersect_SP(t,points[k])){
						data[i][j]|=1<<k;
					}
				}
				if(__builtin_popcount(data[i][j])<=1){
					data[i][j]=0;
				}
				data[j][i]=data[i][j];
			}
		}
		REP(i,pts.size()){
			next[i].clear();
			REP(j,pts.size()){
				if(data[i][j]){
					next[i].push_back(j);
				}
			}
		}
		solve();
	}
}