Cod sursa(job #1882123)

Utilizator marcdariaDaria Marc marcdaria Data 16 februarie 2017 23:03:55
Problema Robot Scor 100
Compilator cpp Status done
Runda becreative17 Marime 7.59 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#define INF 100000000000000000LL

using namespace std;
ifstream fin("robot.in");
ofstream fout("robot.out");

vector< pair<int, int> > R, V[30];
set<pair<int, int> > Set;
pair<int, int> S[100010];
pair<int, int> aux;
vector<pair<int, pair<int, int> > > W;
vector<pair<int, double> > L[4001];
queue<int> Q;
int n, m, k, t, i, j, x, y, p, mx, my, dW, nrpi;

bool ok[4001][4001];
bitset<4001> IQ;
double D[4001];

int det(const pair<int, int> &a, const pair<int, int> &b, const pair<int, int> &c) {
    return (b.first-a.first)*(c.second-a.second) - (c.first-a.first)*(b.second-a.second);
}


int cmp( const pair<int, int> &a, const pair<int, int> &b  ) {
    return det(aux, a, b) > 0;
}

int punctInPoligon(pair<int, int> p, vector<pair<int, int> > v) {
    // -1 afara, 0 pe contur, 1 inauntru
    int semn;
    int poz = 0, neg = 0, nul = 0;

    if (v[v.size()-1]!= v[0]) {
        semn = det(v[v.size()-1], v[0], p);
        if (semn == 0) {
            nul++;
        } else
            if (semn < 0)
                neg++;
            else
                poz++;
    }
    for (int i=0;i<v.size()-1;i++) {
        semn = det(v[i], v[i+1], p);
        if (semn == 0) {
            nul++;
        } else
            if (semn < 0)
                neg++;
            else
                poz++;
    }
    if (neg > 0)
        return -1;

    if (nul != 0)
        return 0;

    return 1;
}


inline int modul(int a) {
    return (a > 0 ? a : -a);
}

double dist(const pair<int, int> &a, const pair<int, int> &b) {
    return sqrt ((a.first-b.first) * (a.first-b.first) +
                (a.second-b.second) * (a.second-b.second));
}

int intersectieSegmentPoligon(int i, int j, int k) {
    // 0 segmentul nu intersecteaza interiorul poligonului
    // 1 segmentul intersecteaza interiorul poligonului

    int xi = punctInPoligon(W[i].second, V[k]);
    int xj = punctInPoligon(W[j].second, V[k]);

// cel putin un punct in poligon
    if (xi == 1 || xj == 1)
        return 1;
//capetele segmentului sunt puncte ale poligonului
    if (W[i].first == k && W[j].first == k) {
        if (modul(i-j) == 1 || ( (W[i-1].first!=k) &&  (W[j+1].first!=k)  ))
            return 0;
        else
            return 1;
    }
    int poz = 0;
    int neg = 0;
    int nul = 0;
    int semn;
    for (int t=0; t<V[k].size(); t++) {
        semn = det(W[i].second, W[j].second, V[k][t]);
        if (semn == 0)
            nul++;
        else
            if (semn > 0)
                poz++;
            else
                neg++;
    }
    if (poz == 0 || neg == 0)
        return 0;

// caut o latura a poligonului fata de care amandoua capetele segmentului sunt in planul negativ
    int gasit = 0;
    for (int t=0;t<V[k].size()-1;t++) {
        if (det(V[k][t], V[k][t+1], W[i].second) <= 0 && det(V[k][t], V[k][t+1], W[j].second) <= 0) {
            gasit = 1;
            break;
        }
    }

    if (gasit == 1)
        return 0;
    else
        return 1;


}

int main() {
    fin>>n;
    mx = my = INF;

    for (i=1;i<=n;i++) {
        fin>>x>>y;
        mx = min(mx, x);
        my = min(my, y);
        R.push_back(make_pair(x, y));
    }

    int p0 = 0;
    for (i=1;i<R.size();i++)
        if ((R[i].first < R[p0].first) || ((R[i].first == R[p0].first) && (R[i].second < R[p0].second)))
            p0 = i;

    pair<int, int> O = make_pair(mx, my);

    fin>>m;
    for (i=1;i<=m;i++) {
        fin>>p;
        for (j=1;j<=p;j++) {
            fin>>x>>y;
            V[i].push_back(make_pair(x, y));
        }
    }

    for (i=1;i<=m;i++) {
        Set.clear();

        for (j=0;j<V[i].size();j++) {
            for (k = 0; k<R.size(); k++) {
                //suprapun punctul k al robotelului peste
                //punctul j al poligonului i
//

                int Ok = 1;
                int pip, poz = 0, neg = 0, nul = 0;
                for (t=0;t<R.size();t++) {
                    pair<int, int> r = make_pair( V[i][j].first + (R[t].first-R[k].first), V[i][j].second + (R[t].second-R[k].second) );
                    pip = punctInPoligon(r, V[i]);
                    if (pip == 0)
                        nul++;
                    else
                        if (pip == 1)
                            poz++;
                        else
                            neg++;
                }
                if (poz > 0)
                    Ok = 0;

                if (neg == 0)
                    Ok = 0;

                if (!Ok)
                    continue;
                pair<int, int> q = make_pair( V[i][j].first - (R[k].first-O.first), V[i][j].second - (R[k].second-O.second) );
                Set.insert(q);
/*
                for (t=0;t<R.size();t++) {
                    Set.insert(make_pair( V[i][j].first + (R[t].first-R[k].first), V[i][j].second + (R[t].second-R[k].second) ));
                }
*/
            }
        }
        V[i].clear();
        for (set<pair<int, int> >::iterator it = Set.begin(); it!= Set.end(); it++) {
            V[i].push_back(*it);
        }

    }

    for (i=1;i<=m;i++) {
        // infasuratoarea convexa a punctelor din vectorul V[i]
        p = 0;
        for (j=0; j<V[i].size(); j++)
            if (V[i][j].first < V[i][p].first ||
                (V[i][j].first == V[i][p].first && V[i][j].second < V[i][p].second))
                p = i;

        aux = V[i][p];
        V[i][p] = V[i][0];
        V[i][0] = aux;

        sort(V[i].begin()+1, V[i].end(), cmp);


        S[1] = V[i][0];
        S[2] = V[i][1];
        k = 2;

        for (j=2;j<V[i].size();j++) {
            while (k >= 2 && det(S[k-1], S[k], V[i][j]) <= 0  ) {
                k--;
            }
            S[++k] = V[i][j];
        }

        V[i].clear();
        for (j=1;j<=k;j++)
            V[i].push_back(S[j]);
        V[i].push_back(V[i][0]);
    }

    W.push_back(make_pair(0, make_pair(mx, my) ));
    for (i=1;i<=m;i++)
        for (j=0;j<V[i].size();j++) {
            W.push_back(make_pair(i, V[i][j] ));
        }
    fin>>x>>y;
    W.push_back(make_pair(m+1, make_pair(x, y) ));
    dW = W.size();


    for (i=0;i<dW-1;i++)
        for (j=i+1;j<=dW-1;j++) {
            //testez segmentul format de W[i].second si W[j].second
            //cout<<i<<" "<<j<<"\n";
            nrpi = 0;
            for (k=1;k<=m;k++){

                if ( intersectieSegmentPoligon(i, j, k) ) {
                    nrpi = 1;
                    break;
                }

            }
            if (nrpi == 0) {
                ok[i][j] = 1;
                ok[j][i] = 1;
            }
        }

    for (i=0;i<dW;i++)
        for (j=0;j<dW;j++)
            if (ok[i][j]) {
                L[i].push_back(make_pair(j, dist(W[i].second, W[j].second)));
            }

    for (i=0;i<dW;i++)
        D[i] = INF;
    int nod, fiu;
    D[0] = 0;
    Q.push(0);
    IQ[0] = 1;
    while (!Q.empty()) {
        nod = Q.front();
        Q.pop();
        IQ[nod] = 0;
        for (i=0;i<L[nod].size();i++) {
            fiu = L[nod][i].first;
            if (D[fiu] > D[nod] + L[nod][i].second) {
                D[fiu] = D[nod] + L[nod][i].second;
                if (!IQ[fiu]) {
                    Q.push(fiu);
                    IQ[fiu] = 1;
                }
            }
        }
    }

    fout<<setprecision(4)<<fixed<<D[dW-1];

    return 0;
}