SHARE
TWEET

C++ solution for problem E (with Floyd Warshall)

ahmed_aly Apr 13th, 2011 671 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.                 for (int i = 0; i < n + 4; i++) {
  93.                         for (int j = 0; j < n + 4; j++)
  94.                                 mat[i][j] = 1 << 30;
  95.                         mat[i][i] = 0;
  96.                 }
  97.                 if (comp(len(p2, st), len(p1, st)) < 0)
  98.                         swap(p1, p2);
  99.                 mat[0][2] = mat[2][0] = len(st, p1);
  100.                 mat[1][3] = mat[3][1] = len(en, p2);
  101.                 mat[2][3] = mat[3][2] = len(p1, p2) * 2;
  102.                 for (int i = 0; i < n; i++) {
  103.                         int i1 = i + 4;
  104.                         int i2 = (i + 1) % n + 4;
  105.                         mat[i1][i2] = mat[i2][i1] = len(pol[i1 - 4], pol[i2 - 4]);
  106.                         if (pointOnSeg(pol[i1 - 4], pol[i2 - 4], p1)) {
  107.                                 if (pointOnSeg(pol[i1 - 4], pol[i2 - 4], p2))
  108.                                         goto PRINT;
  109.                                 mat[2][i1] = mat[i1][2] = len(pol[i1 - 4], p1);
  110.                                 mat[2][i2] = mat[i2][2] = len(pol[i2 - 4], p1);
  111.                         }
  112.                         if (pointOnSeg(pol[i1 - 4], pol[i2 - 4], p2)) {
  113.                                 mat[3][i1] = mat[i1][3] = len(pol[i1 - 4], p2);
  114.                                 mat[3][i2] = mat[i2][3] = len(pol[i2 - 4], p2);
  115.                         }
  116.                 }
  117.                 n += 4;
  118.                 for (int k = 0; k < n; k++)
  119.                         for (int i = 0; i < n; i++)
  120.                                 for (int j = 0; j < n; j++)
  121.                                         mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
  122.                 ret = mat[0][1];
  123.         }
  124.         PRINT: ;
  125.         printf("%.9lf\n", ret);
  126.         return 0;
  127. }
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