Conveyor Belt (UVa Live Archive World Finals 2008 Banff)
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=42&page=show_problem&problem=2121
実装：45分 デバッグ：1時間45分
問題
シャフトがn個あり、このシャフト間をベルトで結んでsからeのシャフトを結びたい。ただしベルトが交差したり、ベルトとシャフトが交差したり、ベルトの空中に浮かんでる長さがd以上になったり、逆回転してるシャフトへベルトを巻き付けたり接触したりしてはいけない。ベルトの長さの最小値を求めよ。
1<=n<=20
解法
コーナーケースに気をつけて探索するだけ。ただし、TLEを回避するためシャフト間を結ぶベルトは前計算しておいたり、現在の答えを超えた場合は探索を打ち切る等すること。
コーナーケースとしては
などがある。
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h> #include <assert.h> #include <vector> #include <queue> #include <string> #include <map> #include <set> using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-7; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) #include <complex> typedef complex<double> Point; typedef vector<Point> Polygon; static const double INF = 1e+5; #define CURR(P, i) (P[i]) #define NEXT(P, i) (P[(i + 1) % P.size()]) struct Line : public vector<Point> { Line() {;} Line(Point a, Point b) { push_back(a); push_back(b); } }; struct Circle { Point p; double r; int dir; // 1, -1 Circle() {;} Circle(Point p, double r, int dir) : p(p), r(r), dir(dir) {;} }; namespace std { bool operator<(const Point &lhs, const Point &rhs) { return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real(); } } 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 int ccw(Point a, Point b, Point c) { b -= a; c -= a; if (cross(b, c) > 0) { return 1; } if (cross(b, c) < 0) { return -1; } if (dot(b, c) < 0) { return 2; } if (norm(b) < norm(c)) { return -2; } return 0; } bool intersectSS(const Line &s, const Line &t) { return ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) < 0 && ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) < 0; } bool intersectSP(const Line &s, const Point &p) { return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; } Point projection(const Line &l, const Point &p) { double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]); return l[0] + t * (l[0] - l[1]); } double distanceSP(const Line &s, const Point &p) { const Point r = projection(s, p); if (intersectSP(s, r)) { return abs(r - p); } return min(abs(s[0] - p), abs(s[1] - p)); } //include inside bool intersectSC(const Line &s, const Circle &c) { return distanceSP(s, c.p) - c.r <= -EPS; } Point AsiLC(const Line &l, const Circle &c) { return projection(l, c.p); } vector<Line> tangentCP(const Circle &c, const Point &p) { vector<Line> ret; Point vect = c.p - p; double d = abs(vect); double l = sqrt(norm(vect) - c.r * c.r); if (isnan(l)) { return ret; } Point v1 = vect * Point(l / d, c.r / d); Point v2 = vect * Point(l / d, -c.r / d); ret.push_back(Line(p - v1 * INF, p + v1 * INF)); if (l > EPS) { ret.push_back(Line(p - v2 * INF, p + v2 * INF)); } return ret; } vector<Line> tangentCC(const Circle &c1, const Circle &c2) { vector<Line> ret; if (abs(c1.p - c2.p) - (c1.r + c2.r) > -EPS) { Point center = (c1.p * c2.r + c2.p * c1.r) / (c1.r + c2.r); ret = tangentCP(c1, center); } if (fabs(c1.r - c2.r) > EPS) { Point out = (-c1.p * c2.r + c2.p * c1.r) / (c1.r - c2.r); vector<Line> nret = tangentCP(c1, out); ret.insert(ret.end(), nret.begin(), nret.end()); } else { Point vect = c2.p - c1.p; vect /= abs(vect); Point q1 = c1.p + vect * Point(0, 1) * c1.r; Point q2 = c1.p + vect * Point(0, -1) * c1.r; ret.push_back(Line(q1 - vect * INF, q1 + vect * INF)); ret.push_back(Line(q2 - vect * INF, q2 + vect * INF)); } return ret; } vector<Line> Normalize(const vector<Line> &ls, const Circle &c1, const Circle &c2) { vector<Line> ret; FORIT(it, ls) { Point p1 = AsiLC(*it, c1); Point p2 = AsiLC(*it, c2); ret.push_back(Line(p1, p2)); } return ret; } Point tan(const Circle &c, const Point &p) { Point vect = p - c.p; vect /= abs(vect); vect *= Point(0, c.dir); return vect; } bool DirectionCheck(const Line &l, const Circle &c1, const Circle &c2) { Point vect = l[1] - l[0]; vect /= abs(vect); return dot(vect, tan(c1, l[0])) >= -EPS && dot(vect, tan(c2, l[1])) >= EPS; } int n; char str[100]; Circle cs[100]; int start, end; double D; double ans; Line conveyor[100]; Line belt[30][30]; bool ok[30][30]; void CalcBelt() { REP(i, n) { REP(j, n) { if (i == j) { continue; } const Circle c1 = cs[i]; const Circle c2 = cs[j]; vector<Line> ls = tangentCC(c1, c2); ls = Normalize(ls, c1, c2); Line l; FORIT(it, ls) { if (DirectionCheck(*it, c1, c2)) { assert(l.size() == 0); l = *it; } } assert(l.size() != 0); if (abs(l[1] - l[0]) - D > -EPS) { goto next; } REP(k, n) { if (intersectSC(l, cs[k])) { goto next; } double d = distanceSP(l, cs[k].p) - cs[k].r; if (d > EPS) { continue; } // touch but reverse direction Point p = projection(l, cs[k].p); Point t = tan(cs[k], p); Point vect = l[1] - l[0]; vect /= abs(vect); if (dot(vect, t) <= -EPS) { goto next; } } ok[i][j] = true; belt[i][j] = l; next:; } } } double calc(int depth, double dist, int use, int from, Point &p); double NextState(int depth, double dist, int use, int from, int to, Point &p) { if (!ok[from][to]) { return 1e+100; } const Circle c1 = cs[from]; const Circle c2 = cs[to]; Line l = belt[from][to]; assert(l.size() == 2); REP(i, depth) { if (intersectSS(l, conveyor[i])) { return 1e+100; } } double ndist = dist + abs(l[1] - l[0]); if (from != start) { double theta = arg(l[0] - c1.p) - arg(p - c1.p); if (theta < 0.0) { theta += 2 * PI; } if (cs[from].dir == -1) { theta = 2 * PI - theta; } if (theta - 2 * PI >= -EPS) { theta = 0; } ndist += theta * c1.r; } conveyor[depth] = l; return calc(depth + 1, ndist, use, to, l[1]); } double calc(int depth, double dist, int use, int from, Point &p) { if (dist > ans) { return 1e+100; } if (from == end) { return ans = min(ans, dist); } double ret = 1e+100; ret = min(ret, NextState(depth, dist, use | (1 << end), from, end, p)); REP(i, n) { if ((use >> i) & 1) { continue; } if (i == end) { continue; } ret = min(ret, NextState(depth, dist, use | (1 << i), from, i, p)); } return ret; } int main() { int test_case = 0; while (scanf("%d", &n), n) { MEMSET(ok, false); test_case++; REP(i, n) { int dir = 1; double x, y, r; scanf("%lf %lf %lf %s", &x, &y, &r, str); if (strlen(str) == 1) { dir = -1; } cs[i] = Circle(Point(x, y), r, dir); } scanf("%d %d %lf", &start, &end, &D); CalcBelt(); ans = 1e+100; Point p(0, 0); calc(0, 0, 1 << start, start, p); if (ans < 1e+10) { int v = round(ans * 100); printf("Case %d: length = %d", test_case, v / 100); if (v % 100 != 0) { printf(".%02d", v % 100); } puts(""); } else { printf("Case %d: Cannot reach destination shaft\n", test_case); } } }
