Advertisement
ahmed_aly

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

Apr 13th, 2011
1,066
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement