SHARE
TWEET

C++ solution for problem E

ahmed_aly Apr 13th, 2011 290 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstring>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <sstream>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <set>
  16. #include <complex>
  17. #include <list>
  18. #include <climits>
  19. #include <cctype>
  20.  
  21. using namespace std;
  22.  
  23. typedef complex<double> point;
  24. #define cross(a,b) ((conj(a)*(b)).imag())
  25. #define X real()
  26. #define Y imag()
  27.  
  28. const double eps = 1e-9;
  29.  
  30. int comp(double a, double b) {
  31.         if (fabs(a - b) < eps)
  32.                 return 0;
  33.         return a > b ? 1 : -1;
  34. }
  35.  
  36. struct pComp {
  37.         bool operator()(const point &A, const point &B) const {
  38.                 if (comp(A.X, B.X))
  39.                         return A.X < B.X;
  40.                 if (comp(A.Y, B.Y))
  41.                         return A.Y < B.Y;
  42.                 return 0;
  43.         }
  44. };
  45.  
  46. double len(point A, point B) {
  47.         return hypot(A.X - B.X, A.Y - B.Y);
  48. }
  49.  
  50. bool pointOnSeg(point A, point B, point R) {
  51.         return comp(len(A, B), len(A, R) + len(B, R)) == 0;
  52. }
  53.  
  54. bool lineInter(point A, point B, point P, point Q, point &R) {
  55.         double d1 = cross(P-A,B-A);
  56.         double d2 = cross(Q-A,B-A);
  57.         if (comp(d1, d2) == 0)
  58.                 return false;
  59.         R = (d1 * Q - d2 * P) / (d1 - d2);
  60.         if (!pointOnSeg(A, B, R) || !pointOnSeg(P, Q, R))
  61.                 return false;
  62.         return true;
  63. }
  64.  
  65. int n;
  66. point st, en;
  67. vector<point> pol;
  68.  
  69. double mat[34][34];
  70.  
  71. int main() {
  72.         int x, y;
  73.         cin >> x >> y;
  74.         st = point(x, y);
  75.         cin >> x >> y;
  76.         en = point(x, y);
  77.         cin >> n;
  78.         for (int i = 0; i < n; i++) {
  79.                 cin >> x >> y;
  80.                 pol.push_back(point(x, y));
  81.         }
  82.         double ret = len(st, en);
  83.         set<point, pComp> intrs;
  84.         for (int i = 0; i < n; i++) {
  85.                 point R;
  86.                 if (lineInter(st, en, pol[i], pol[(i + 1) % n], R))
  87.                         intrs.insert(R);
  88.         }
  89.         if (intrs.size() == 2) {
  90.                 point p1 = *intrs.begin();
  91.                 point p2 = *(++intrs.begin());
  92.                 double d1 = -1, d2 = 0;
  93.                 for (int i = 0; i < n; i++) {
  94.                         int j = (i + 1) % n;
  95.                         d2 += len(pol[i], pol[j]);
  96.                         if (d1 == -1 && pointOnSeg(pol[i], pol[j], p1)) {
  97.                                 if (pointOnSeg(pol[i], pol[j], p2))
  98.                                         goto PRINT;
  99.                                 d1 = len(p1, pol[j]);
  100.                                 while (1) {
  101.                                         int j2 = (j + 1) % n;
  102.                                         if (pointOnSeg(pol[j], pol[j2], p2)) {
  103.                                                 d1 += len(pol[j], p2);
  104.                                                 break;
  105.                                         }
  106.                                         d1 += len(pol[j], pol[j2]);
  107.                                         j = j2;
  108.                                 }
  109.                         }
  110.                 }
  111.                 d2 -= d1;
  112.                 double d3 = len(p1, p2);
  113.                 ret -= d3;
  114.                 d3 *= 2;
  115.                 ret += min(d3, min(d1, d2));
  116.         }
  117.         PRINT: ;
  118.         printf("%.9lf\n", ret);
  119.         return 0;
  120. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top