Advertisement
jonathanasdf

2012 WF H

Jun 25th, 2013
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <iomanip>
  2. #include <iostream>
  3. #include <vector>
  4. #include <complex>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. typedef long double ld;
  9. typedef complex<ld> pt;
  10. const ld INF = 1e12, EPS = 1e-9;
  11. inline ld cp(const pt &a, const pt &b) { return a.real()*b.imag() - b.real()*a.imag();}
  12. inline ld sgn(const ld& x) { return abs(x) < EPS ? 0 : x/abs(x); }
  13. inline bool cmp_lex(const pt& a, const pt& b)
  14. { return a.real() < b.real() || (a.real() == b.real() && a.imag() < b.imag()); }
  15.  
  16. // SIGNED distance. Pt on the right of vector (a -> b) will be NEGATIVE.
  17. inline ld lp_dist(const pt &a, const pt &b, const pt &p){
  18.   return cp(b - a, p - a) / abs(b - a); }
  19.  
  20. // flips point p across vector a->b
  21. inline pt flip(const pt& p, const pt& a, const pt& b) {
  22.   ld d = lp_dist(a, b, p);
  23.   return p-2*d*(b-a)*pt(0,1)/abs(b-a); }
  24.  
  25. // handles ALL cases, change occurrences of <= to < to exclude endpoints
  26. bool seg_x_seg(pt a1, pt a2, pt b1, pt b2){
  27.   //if (a1==a2 || b1==b2) return false; // uncomment to exclude endpoints
  28.   int s1 = sgn(cp(a2 - a1, b1 - a1)), s2 = sgn(cp(a2 - a1, b2 - a1));
  29.   int s3 = sgn(cp(b2 - b1, a1 - b1)), s4 = sgn(cp(b2 - b1, a2 - b1));
  30.   if(!s1 && !s2 && !s3) { // collinear
  31.     if (cmp_lex(a2, a1)) swap(a1,a2); if (cmp_lex(b2, b1)) swap(b1, b2);
  32.     return !cmp_lex(b2, a1) && !cmp_lex(a2, b1);
  33.     //return cmp_lex(a1, b2) && cmp_lex(b1, a2);//uncomment to exclude endpoints
  34.   } return s1*s2 <= 0 && s3*s4 <= 0; }
  35.  
  36. int main() {
  37.     int N; int zz=1;
  38.     while(cin >> N) {
  39.         vector<pt> v;
  40.         int px, py; cin >> px >> py;
  41.         for (int i=0; i < N; i++) {
  42.             int x, y; cin >> x >> y;
  43.             v.push_back(pt(x, y));
  44.         }
  45.        
  46.         ld res = INF;
  47.         ld dp[N+3];
  48.         for (int cnt=0; cnt < N; cnt++) {
  49.             v.push_back(v.front());
  50.             v.insert(v.begin(), pt(px, py));
  51.             v.push_back(pt(px, py));
  52.  
  53.             vector<pt> v2(v.begin(), v.end());
  54.             for (int i=0; i < N+2; i++)
  55.                 for (int j=i+1; j <= N+2; j++)
  56.                     v2[j] = flip(v2[j], v2[i], v2[i+1]);
  57.  
  58.             dp[0] = 0;
  59.             for (int i=1; i <= N+2; i++) {
  60.                 dp[i] = INF;
  61.                 for (int j=0; j < i; j++) {
  62.                     if (dp[j] + abs(v2[j]-v2[i]) < dp[i]) {
  63.                         bool good = true;
  64.                         for (int k=j; k+1 <= i; k++)
  65.                             good &= seg_x_seg(v2[j], v2[i], v2[k], v2[k+1]);
  66.                         if (good) dp[i] = dp[j] + abs(v2[j]-v2[i]);
  67.                     }
  68.                 }
  69.             }
  70.             res = min(res, dp[N+2]);
  71.  
  72.             v.pop_back();
  73.             v.erase(v.begin());
  74.             v.erase(v.begin());
  75.         }
  76.         cout << "Case " << zz++ << ": " << fixed << setprecision(2) << res << endl;        
  77.     }
  78.     return 0;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement