Cod sursa(job #2351537)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 22 februarie 2019 15:07:29
Problema Robot Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.46 kb
#include <bits/stdc++.h>
#define x real()
#define y imag()
#define no_sol { cout << "-1\n"; exit(0); }

using namespace std;

typedef long double ld;
typedef complex<ld> point;

const ld inf = 1e9, eps = 1e-7;

int before[30], M;
vector< pair<int, ld> > v[505];
ld dist[505];

vector<point> pct;

bool is_zero(ld X) { return (X < eps && X > -eps); }

bool cmp(pair<point, int> a, pair<point, int> b)
{
    return arg(a.first) < arg(b.first);
}

bool on_segm(point P, point A, point B)
{
    return is_zero(abs(A - P) + abs(B - P) - abs(A - B));
}

ld cross(point A, point B)
{
    return (conj(A) * B).imag();
}

struct polig
{
    int n;
    point p[505];

    void read()
    {
        int i; ld X, Y;
        cin >> n;
        for(i=1; i<=n; ++i)
        {
            cin >> X >> Y;
            p[i] = {X, Y};
        }
        p[0] = p[n]; p[n+1] = p[1];
    }

    void create(polig &A, polig &B)
    {
        vector< pair<point, int> > edges;

        int i, j;
        for(i=1; i<=B.n; ++i) edges.push_back({ B.p[i+1] - B.p[i], -i }); /// trigonometric
        for(i=1; i<=A.n; ++i) edges.push_back({ A.p[i-1] - A.p[i], i }); /// antitrigonometric

        sort(edges.begin(), edges.end(), cmp);

        for(i=0; i<A.n + B.n; ++i) edges.push_back(edges[i]);

        point Ref, Start;
        for(i=0; i<edges.size(); ++i)
            if(edges[i].second >= 0 && edges[i+1].second < 0)
            {
                Ref = A.p[edges[i].second];
                Start = B.p[-edges[i+1].second];
                break;
            }

        for(j=i+1; j<=i+A.n+B.n; ++j)
        {
            p[++n] = Start - Ref;
            Start += edges[j].first;
        }

        p[0] = p[n]; p[n+1] = p[1];
    }

    bool interior(point a)
    {
        int i;
        for(i=1; i<=n; ++i)
            if(cross(p[i] - a, p[i+1] - a) < eps) return 0;
        return 1;
    }

} robot, obs[30], poly[30];


void add_edge(int a, int b)
{
    ld Dist = abs(pct[a] - pct[b]);
    v[a].push_back({b, Dist});
    v[b].push_back({a, Dist});
}

bool intersect(point A, point B, point C, point D)
{
    point Dif = A - C, D1 = B - A, D2 = D - C;

    ld delta = cross(D1, D2);
    if(is_zero(delta)) return 0; /// paralele

    ld r = cross(Dif, D2) / delta, s = cross(D1, Dif) / delta;
    return (r > eps && r < 1 - eps && s > eps && s < 1 - eps);
}

bool correct(point A, point B)
{
    int i, j;
    for(i=1; i<=M; ++i)
    {
        for(j=1; j<=poly[i].n; ++j)
            if(poly[i].p[j] != A && poly[i].p[j] != B && on_segm(poly[i].p[j], A, B)) return 0;

        for(j=1; j<=poly[i].n; ++j)
            if(intersect(A, B, poly[i].p[j], poly[i].p[j+1])) return 0;

        if(poly[i].interior((ld) 0.43 * A + (ld) 0.57 * B)) return 0;
    }
    return 1;
}

void add_edges(point S, point F)
{
    pct.push_back(S); pct.push_back(F);

    int i, j, k;
    for(i=1; i<=M; ++i)
        for(j=1; j<=poly[i].n; ++j)
        {
            bool ok = 1;
            for(k=1; ok && k<=M; ++k)
                if(poly[k].interior(poly[i].p[j])) ok = 0;

            if(ok) pct.push_back(poly[i].p[j]);
        }

    for(i=1; i<=M; ++i)
        if(poly[i].interior(F)) no_sol;

    for(i=0; i<pct.size(); ++i)
        for(j=i+1; j<pct.size(); ++j)
            if(correct(pct[i], pct[j]))
                add_edge(i, j);
}

void solve(int start, int finish)
{
    priority_queue< pair<ld, int>, vector< pair<ld, int> >, greater< pair<ld, int> > > heap;

    int node, i; ld D;
    for(i=0; i<pct.size(); ++i) dist[i] = inf;

    dist[start] = 0;
    heap.push({0, start});

    while(heap.size())
    {
        tie(D, node) = heap.top();
        heap.pop();
        if(dist[node] != D) continue;

        for(auto it : v[node])
            if(dist[it.first] > dist[node] + it.second)
            {
                dist[it.first] = dist[node] + it.second;
                heap.push({ dist[it.first], it.first });
            }
    }

    if(is_zero(dist[finish] - inf)) no_sol;
    cout << setprecision(5) << fixed;
    cout << dist[finish] << '\n';
}

int main()
{
    freopen("robot.in", "r", stdin);
    freopen("robot.out", "w", stdout);

    robot.read();
    int i;
    ld xi, yi, xf, yf;

    cin >> M;
    for(i=1; i<=M; ++i) obs[i].read();

    xi = yi = inf;
    for(i=1; i<=M; ++i)
    {
        xi = min(xi, robot.p[i].x);
        yi = min(yi, robot.p[i].y);
    }
    for(i=1; i<=M; ++i) robot.p[i] -= point(xi, yi);

    for(i=1; i<=M; ++i)
        poly[i].create(robot, obs[i]);

    cin >> xf >> yf;

    add_edges({xi, yi}, {xf, yf});
    solve(0, 1);

    return 0;
}