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

#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <complex>
#include <list>
#include <climits>
#include <cctype>

using namespace std;

typedef complex<double> point;
#define cross(a,b) ((conj(a)*(b)).imag())
#define X real()
#define Y imag()

const double eps = 1e-9;

int comp(double a, double b) {
    if (fabs(a - b) < eps)
        return 0;
    return a > b ? 1 : -1;
}

struct pComp {
    bool operator()(const point &A, const point &B) const {
        if (comp(A.X, B.X))
            return A.X < B.X;
        if (comp(A.Y, B.Y))
            return A.Y < B.Y;
        return 0;
    }
};

double len(point A, point B) {
    return hypot(A.X - B.X, A.Y - B.Y);
}

bool pointOnSeg(point A, point B, point R) {
    return comp(len(A, B), len(A, R) + len(B, R)) == 0;
}

bool lineInter(point A, point B, point P, point Q, point &R) {
    double d1 = cross(P-A,B-A);
    double d2 = cross(Q-A,B-A);
    if (comp(d1, d2) == 0)
        return false;
    R = (d1 * Q - d2 * P) / (d1 - d2);
    if (!pointOnSeg(A, B, R) || !pointOnSeg(P, Q, R))
        return false;
    return true;
}

int n;
point st, en;
vector<point> pol;

double mat[34][34];

int main() {
    int x, y;
    cin >> x >> y;
    st = point(x, y);
    cin >> x >> y;
    en = point(x, y);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        pol.push_back(point(x, y));
    }
    double ret = len(st, en);
    set<point, pComp> intrs;
    for (int i = 0; i < n; i++) {
        point R;
        if (lineInter(st, en, pol[i], pol[(i + 1) % n], R))
            intrs.insert(R);
    }
    if (intrs.size() == 2) {
        point p1 = *intrs.begin();
        point p2 = *(++intrs.begin());
        for (int i = 0; i < n + 4; i++) {
            for (int j = 0; j < n + 4; j++)
                mat[i][j] = 1 << 30;
            mat[i][i] = 0;
        }
        if (comp(len(p2, st), len(p1, st)) < 0)
            swap(p1, p2);
        mat[0][2] = mat[2][0] = len(st, p1);
        mat[1][3] = mat[3][1] = len(en, p2);
        mat[2][3] = mat[3][2] = len(p1, p2) * 2;
        for (int i = 0; i < n; i++) {
            int i1 = i + 4;
            int i2 = (i + 1) % n + 4;
            mat[i1][i2] = mat[i2][i1] = len(pol[i1 - 4], pol[i2 - 4]);
            if (pointOnSeg(pol[i1 - 4], pol[i2 - 4], p1)) {
                if (pointOnSeg(pol[i1 - 4], pol[i2 - 4], p2))
                    goto PRINT;
                mat[2][i1] = mat[i1][2] = len(pol[i1 - 4], p1);
                mat[2][i2] = mat[i2][2] = len(pol[i2 - 4], p1);
            }
            if (pointOnSeg(pol[i1 - 4], pol[i2 - 4], p2)) {
                mat[3][i1] = mat[i1][3] = len(pol[i1 - 4], p2);
                mat[3][i2] = mat[i2][3] = len(pol[i2 - 4], p2);
            }
        }
        n += 4;
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
        ret = mat[0][1];
    }
    PRINT: ;
    printf("%.9lf\n", ret);
    return 0;
}