/* @file spiral.cc @brief Solves "Spiral Footrace" ( http://www.acm-japan.org/past-icpc/domestic1999/D.htm ) @author Yuta Kitamura @date 2005-04-30 */ // start 18:26 // try again 20:18 // end 23:23 #include #include #include #include using std::cout; using std::cin; using std::endl; using std::set; using std::min; using std::sqrt; using std::ostream; typedef unsigned int uint; class Rational { mutable long long n_; // denominator, numerator mutable unsigned long long d_; public: Rational() : d_(0), n_(1) {} Rational(long long n, unsigned long long d) : n_(n), d_(d) { assert(d_ != 0); rationalize(); return; } Rational(const Rational& rhs) : n_(rhs.n_), d_(rhs.d_) {} Rational operator+ (const Rational& rhs) const { return Rational(n_ * rhs.d_ + rhs.n_ * d_, d_ * rhs.d_); } Rational operator- (const Rational& rhs) const { return Rational(n_ * rhs.d_ - rhs.n_ * d_, d_ * rhs.d_); } Rational operator* (const Rational& rhs) const { return Rational(n_ * rhs.n_, d_ * rhs.d_); } Rational operator/ (const Rational& rhs) const { return Rational(n_ * rhs.d_, d_ * rhs.n_); } bool operator< (const Rational& rhs) const { //cout << "op< " << *this << " (" << this->n_ << "/" << this->d_ << "), " // << rhs << " (" << rhs.n_ << "/" << rhs.d_ << "), "; Rational diff = *this - rhs; //cout << diff << " (" << diff.n_ << "/" << diff.d_ << ")" << endl; return diff.n_ < 0; } bool operator== (const Rational& rhs) const { // return !(*this < rhs || rhs < *this); Rational diff = *this - rhs; return diff.n_ == 0; } bool operator>= (const Rational& rhs) const { return !(*this < rhs); } bool operator> (const Rational& rhs) const { return rhs < *this; } bool operator<= (const Rational& rhs) const { return !(*this > rhs); } bool operator!= (const Rational& rhs) const { return !(*this == rhs); } private: static uint gcd(unsigned long long i, unsigned long long j) { if (j > i) return gcd(j, i); if (j == 0) return i; else return gcd(j, i % j); } void rationalize() const { // cout << "RATIONALIZE " << n_ << "/" << d_ << " -> "; if (n_ == 0) { d_ = 1; return; } unsigned long long absn = (n_ < 0) ? static_cast(-n_) : static_cast(n_); uint div = gcd(absn, d_); n_ /= static_cast(div); d_ /= div; // cout << n_ << "/" << d_ << endl; return; } friend ostream& operator<< (ostream& ost, const Rational& rhs); }; ostream& operator<< (ostream& ost, const Rational& rhs) { ost << static_cast(rhs.n_) / rhs.d_; return ost; } struct Point { int x, y; bool operator< (const Point& rhs) const { if (x == rhs.x) return y < rhs.y; else return x < rhs.x; } }; Rational calcAngle(Point v) { if (v.x >= 0) { Rational sgn((v.y > 0) ? -1 : 1, 1); return sgn * Rational(v.y * v.y, v.x * v.x + v.y * v.y) - Rational(1, 1); } else { Rational sgn((v.y < 0) ? -1 : 1, 1); return sgn * Rational(v.y * v.y, v.x * v.x + v.y * v.y) + Rational(1, 1); } } double calcLength(set s, Point cur, Point prev) { // cout << "(" << cur.x << ", " << cur.y << ") " << endl; if (s.empty()) return 0.0; Point v; v.x = cur.x - prev.x; v.y = cur.y - prev.y; Rational origin(calcAngle(v)); // cout << "origin " << origin << endl; set::iterator itNext = s.end(); Rational minAngle(1234, 1); // illegal uint distance; for (set::iterator it = s.begin(); it != s.end(); ++it) { Point w; w.x = it->x - cur.x; w.y = it->y - cur.y; Rational angle(calcAngle(w)); uint d = w.x * w.x + w.y * w.y; /* cout << "vector (" << w.x << ", " << w.y << ") angle " << angle << " min " << minAngle << endl; cout << " " << (minAngle == Rational(1234, 1)) << ", " << (angle == minAngle && d < distance) << ", " << (origin <= minAngle && origin <= angle && angle < minAngle) << ", " << (origin > minAngle && !(minAngle < angle && angle < origin)) << endl; */ // 110, 395 if (minAngle == Rational(1234, 1) || (angle == minAngle && d < distance) || (origin <= minAngle && origin <= angle && angle < minAngle) || (origin > minAngle && !(minAngle < angle && angle < origin))) { minAngle = angle; distance = d; itNext = it; } } Point n = *itNext; s.erase(itNext); return sqrt(distance) + calcLength(s, n, cur); } int main() { while (cin) { uint n; cin >> n; if (n == 0) break; set s; for (uint i = 0; i < n; ++i) { Point p; cin >> p.x >> p.y; s.insert(p); } Point fir, bef; fir.x = 0; fir.y = 0; bef.x = 0, bef.y = -1; double l = calcLength(s, fir, bef); cout << static_cast(l * 10.0) / 10 << '.' << static_cast(l * 10.0) % 10 << endl; } return 0; }