Cod sursa(job #1862552)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 30 ianuarie 2017 01:24:58
Problema Robot Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.61 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "robot.in" , ios::in  );
fstream out( "robot.out", ios::out );

vector<vector<pair<int, double>>> gph; vector<double> dp; vector<bool> mrk;
vector<vector<pair<int, int>>> plg; vector<pair<int, int>> rbt, pts; deque<int> que;

int ccw( pair<int, int> p1, pair<int, int> p2, pair<int, int> p3 ) {
    return ( p2.first - p1.first ) * ( p3.second - p1.second ) -
           ( p3.first - p1.first ) * ( p2.second - p1.second );
}

vector<pair<int, int>> nfp( pair<int, int> stp, vector<pair<int, int>> rbt, vector<pair<int, int>> plg ) {
    vector<pair<int, int>> nfp, ans;
    
    for( pair<int, int> pr1 : rbt )
        for( pair<int, int> pr2 : plg )
            nfp.push_back( make_pair( stp.first  + ( pr2.first  - pr1.first  ),
                                      stp.second + ( pr2.second - pr1.second ) ) );
    
    sort( nfp.begin(), nfp.end() );
    vector<int> mrk( nfp.size(), 0 ), stk( 1, 0 );
    
    for( int i = 1, aux = (int) stk.size(); i < nfp.size(); i ++ ) {
        if( mrk[i] == 1 )
            continue;
        
        while( stk.size() > aux && ccw( nfp[stk[stk.size() - 2]], nfp[stk[stk.size() - 1]], nfp[i] ) <= 0 ) {
            mrk[stk.back()] = 0;
            stk.pop_back();
        }
        
        mrk[i] = 1;
        stk.push_back( i );
    }
    
    for( int i = (int) nfp.size() - 1, aux = (int) stk.size(); i > -1; i -- ) {
        if( mrk[i] == 1 )
            continue;
        
        while( stk.size() > aux && ccw( nfp[stk[stk.size() - 2]], nfp[stk[stk.size() - 1]], nfp[i] ) <= 0 ) {
            mrk[stk.back()] = 0;
            stk.pop_back();
        }
        
        mrk[i] = 1;
        stk.push_back( i );
    }
    
    stk.pop_back();
    for( int p : stk )
        ans.push_back( nfp[p] );
    
    return ans;
}

bool osg( pair<int, int> pt1, pair<int, int> pt2, pair<int, int> pt3 ) {
    return ( ( pt1.first  >= min( pt2.first , pt3.first  ) && pt1.first  <= max( pt2.first , pt3.first  ) ) &&
             ( pt1.second >= min( pt2.second, pt3.second ) && pt1.second <= max( pt2.second, pt3.second ) ) &&
             ( ccw( pt1, pt2, pt3 ) == 0 ) );
}

bool ipg( pair<int, int> pt, vector<pair<int, int>> pg ) {
    int arr1 = 0, arr2 = 0, sgn = ( ( ccw( pt, pg[0], pg[1] ) < 0 ) ? -1 : 1 );
    
    for( int i = 0; i < pg.size(); i ++ ) {
        if( pt == pg[i] || osg( pt, pg[i], pg[( i + 1 ) % pg.size()] ) )
            return false;
        
        arr1 += sgn * ccw( pt, pg[i], pg[( i + 1 ) % pg.size()] );
        arr2 += abs(  ccw( pt, pg[i], pg[( i + 1 ) % pg.size()] ) );
    }
    
    return ( arr1 == arr2 );
}

bool isg( pair<int, int> pt1, pair<int, int> pt2, pair<int, int> pt3, pair<int, int> pt4 ) {
    return ( ccw( pt1, pt2, pt3 ) * 1LL * ccw( pt1, pt2, pt4 ) < 0 ) &&
           ( ccw( pt3, pt4, pt1 ) * 1LL * ccw( pt3, pt4, pt2 ) < 0 );
}

int main( void ) {
    ios::sync_with_stdio( false );
    
    int n;
    in >> n;
    
    rbt.resize( n );
    for( pair<int, int> &pr : rbt )
        in >> pr.first >> pr.second;
    
    pair<int, int> stp = make_pair(
        ( *min_element( rbt.begin(), rbt.end(),
            []( pair<int, int> pr1, pair<int, int> pr2 ) {
                return pr1.first  < pr2.first;  } ) ).first,
        ( *min_element( rbt.begin(), rbt.end(),
            []( pair<int, int> pr1, pair<int, int> pr2 ) {
                return pr1.second < pr2.second; } ) ).second );
    pts.push_back( stp );
    
    int m;
    in >> m;
    
    plg.resize( m );
    for( vector<pair<int, int>> &pg : plg ) {
        int k;
        in >> k;
        
        pg.resize( k );
        for( pair<int, int> &pt : pg )
            in >> pt.first >> pt.second;
        
        pg = nfp( stp, rbt, pg );
        
        for( pair<int, int> pt : pg )
            pts.push_back( pt );
    }
    
    pair<int, int> fip;
    in >> fip.first >> fip.second;
    
    pts.push_back( fip );
    gph.resize( pts.size() );
    for( int i = 0; i < pts.size(); i ++ ) {
        for( int j = i + 1; j < pts.size(); j ++ ) {
            bool ok = true;
            
            for( vector<pair<int, int>> pg : plg ) {
                if( ok == true && ( ipg( pts[i], pg ) || ipg( pts[j], pg ) ) )
                    ok = false;
                
                for( int k = 0; k < pg.size() && ok == true; k ++ ) {
                    for( int p = k + 1; p < pg.size() && ok == true; p ++ ) {
                        if( isg( pts[i], pts[j], pg[k], pg[p] ) )
                            ok = false;
                    }
                }
            }
            
            if( ok == true ) {
                gph[i].push_back( make_pair( j, hypot( abs( pts[i].first  - pts[j].first  ),
                                                       abs( pts[i].second - pts[j].second ) ) ) );
                gph[j].push_back( make_pair( i, hypot( abs( pts[i].first  - pts[j].first  ),
                                                       abs( pts[i].second - pts[j].second ) ) ) );
            }
        }
    }
    
    dp.assign( pts.size(), INT_MAX ); mrk.assign( pts.size(), false ); dp[0] = 0;
    for( que.push_back( 0 ), mrk[0] = true; !que.empty(); mrk[que.front()] = false, que.pop_front() ) {
        int x = que.front();
        
        for( pair<int, double> y : gph[x] ) {
            if( dp[y.first] > dp[x] + y.second ) {
                dp[y.first] = dp[x] + y.second;
                
                if( mrk[y.first] == false ) {
                    mrk[y.first] = true;
                    que.push_back( y.first );
                }
            }
        }
    }

    out << setprecision(2) << fixed << ( ( dp.back() == INT_MAX ) ? -1 : dp.back() ) << endl;
    return 0;
}