Cod sursa(job #3264724)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 23 decembrie 2024 16:28:52
Problema Robot Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 7.8 kb
#include <stdio.h>
#include <math.h>

#include <vector>
#include <algorithm>
#include <queue>

using ftype = double;
using ll = long long;

const int INF = 1e9;
const ftype EPS = 1e-4;

struct Point {
  int x, y;
  Point( int x = 0, int y = 0 ): x(x), y(y) {}
  Point operator + ( const Point& that ) const { return Point(x + that.x, y + that.y); }
  Point operator - ( const Point& that ) const { return Point(x - that.x, y - that.y); }
  Point operator += ( const Point& that ) { return *this = *this + that; }
  Point operator -= ( const Point& that ) { return *this = *this - that; }

  bool operator == ( const Point& that ) const { return x == that.x && y == that.y; }
};

int sdet( const Point &a, const Point &b, const Point &c ) {
  ll det = (a.x - b.x) * (ll)(a.y - c.y) - (a.y - b.y) * (ll)(a.x - c.x);

  if( det < 0 ) return -1;
  if( det > 0 ) return +1;
  return 0;
}

using Poly = std::vector<Point>;

Poly hull_half( const std::vector<Point> &points, int sgn ) {
  Poly ret;

  for( Point P : points ){
    while( ret.size() >= 2 && sdet( ret.end()[-2], ret.end()[-1], P ) * sgn <= 0 )
      ret.pop_back();
    ret.push_back( P );
  }

  return ret;
}

Poly hull( std::vector<Point> &points ) {
  std::sort( points.begin(), points.end(), []( const Point &a, const Point &b ) -> bool {
    if( a.x == b.x )
      return a.y < b.y;
    return a.x < b.x;
  } );

  Poly upper = hull_half( points, +1 );
  Poly lower = hull_half( points, -1 );

  upper.insert( upper.end(), lower.rbegin() + 1, lower.rend() - 1 );
  return upper;
}

Poly enlarge_obstacle( const Poly &obs, const Poly &robot ) {
  std::vector<Point> candidates;
  for( Point V : obs )
    for( Point V_rob : robot ){
      // mutam V_rob peste V
      // ne pasa unde ajunge punctul (0, 0)
      // O + V_rob = V_rob
      // O' + V_rob = V
      candidates.push_back( V - V_rob );
    }

  return hull( candidates );
}

struct Seg {
  Point a, b;
  Seg(): a(), b() {}
  Seg( Point a, Point b ): a(a), b(b) {}
  ftype len() { return hypot( a.x - b.x, a.y - b.y ); }
};

template<typename T> bool in_box( T x, T y, const Seg& S ) {
  if( x < S.a.x && x < S.b.x ) return false;
  if( x > S.a.x && x > S.b.x ) return false;

  if( y < S.a.y && y < S.b.y ) return false;
  if( y > S.a.y && y > S.b.y ) return false;

  if( hypot( x - S.a.x, y - S.a.y ) < EPS ) return false;
  if( hypot( x - S.b.x, y - S.b.y ) < EPS ) return false;

  return true;
}

bool in_box( const Point &P, const Seg& S ) {
  return in_box( P.x, P.y, S );
}

// we want the INTERIORS to intersect
bool seg_intersect( const Seg &strips, const Seg &wing ) {
  if( strips.a == strips.b ) return false;
  if( wing.a == wing.b ) return false;

  // printf( "strips = (%d %d) -- (%d %d)\n", strips.a.x, strips.a.y, strips.b.x, strips.b.y );
  // printf( "wing = (%d %d) -- (%d %d)\n", wing.a.x, wing.a.y, wing.b.x, wing.b.y );

  // intersectam dreptele
  // Ax + By + C = 0

  // Axa + Bya + C = 0
  // Axb + Byb + C = 0
  // A(xa - xb) + B(ya - yb) = 0
  // A <- +(ya - yb)
  // B <- -(xa - xb)
  // C = -(ya - yb)xa + +(xa - xb)ya = -yaxa + ybxa + xaya - xbya
  // C = ybxa - xbya

  int stripsA = +(strips.a.y - strips.b.y);
  int stripsB = -(strips.a.x - strips.b.x);
  int stripsC = strips.b.y * strips.a.x - strips.a.y * strips.b.x;

  int wingA = +(wing.a.y - wing.b.y);
  int wingB = -(wing.a.x - wing.b.x);
  int wingC = wing.b.y * wing.a.x - wing.a.y * wing.b.x;

  if( stripsA * (ll)wingB == wingA * (ll)stripsB ){ // segmente paralele
    // printf( "parallel\n" );
    return false; // <----- (!!)
    
    if( !(stripsA * (ll)wingC == wingA * (ll)stripsC && stripsB * (ll)wingC == wingB * (ll)stripsC) )
      return false;

    // segmentele au aceeasi dreapta suport
    if( in_box( strips.a, wing ) ) return true;
    if( in_box( strips.b, wing ) ) return true;
    if( in_box( wing.a, strips ) ) return true;
    if( in_box( wing.b, strips ) ) return true;

    return false;
  }

  // sAx + sBy + sC = 0
  // wAx + wBy + wC = 0
  // -- eliminam x, y
  // (wAsB - sAwB) * y + (wAsC - sAwC) = 0
  // (wBsA - sBwA) * x + (wBsC - sBwC) = 0

  ftype x_int = -(wingB * (ll)stripsC - stripsB * (ll)wingC) / (ftype)(wingB * (ll)stripsA - stripsB * (ll)wingA);
  ftype y_int = -(wingA * (ll)stripsC - stripsA * (ll)wingC) / (ftype)(wingA * (ll)stripsB - stripsA * (ll)wingB);

  // printf( "intersect (%.3lf %.3lf)\n", x_int, y_int );

  return in_box( x_int, y_int, strips ) && in_box( x_int, y_int, wing );
}

std::vector<Seg> dangerous;

bool hits_interior( const Seg& proba ) {
  for( Seg D : dangerous )
    if( seg_intersect( D, proba ) ){
      //printf( "true!! -- (%d %d) -- (%d %d) este rau\n", proba.a.x, proba.a.y, proba.b.x, proba.b.y );
      return true;
    }
  
  return false;
}

namespace Graph {
  std::vector<Point> points;
  int n;

  struct Edge {
    int u;
    ftype cost;
    Edge( int u, ftype cost ): u(u), cost(cost) {}
  };

  // daca tot ai facut problema doar cu std::vector nu mai are rost sa schimbi acum
  std::vector<std::vector<Edge>> adj;

  // points[] si dangerous[] sunt calculate
  void build() {
    n = (int)points.size();
    
    adj.resize( n );
    for( int i = 0; i < n; i++ )
      for( int j = i + 1; j < n; j++ ){
        Seg S(points[i], points[j]);
        if( !hits_interior( S ) ){
          ftype cost = S.len();
          adj[i].emplace_back( j, cost );
          adj[j].emplace_back( i, cost );
        }
      }
  }

  ftype dijkstra( int src, int dest ) {
    std::vector<ftype> dist(n, +INF);

    std::priority_queue<std::pair<ftype, int>> pq;
    pq.emplace( 0, src );
    dist[src] = 0;

    while( !pq.empty() ){
      auto top = pq.top();
      pq.pop();

      int u = top.second;
      if( -dist[u] != top.first ) // trebuie egalitate exacta, nu e nevoie de EPS
        continue;

      for( Edge e : adj[u] ){
        if( dist[u] + e.cost < dist[e.u] ){
          dist[e.u] = dist[u] + e.cost;
          pq.emplace( -dist[e.u], e.u );
        }
      }
    }

    return dist[dest];
  }
}

int main() {
  FILE *fin = fopen( "robot.in", "r" );
  FILE *fout = fopen( "robot.out", "w" );
  
  Poly robot;
  Point start(+INF, +INF);
  { // citim robotul
    int n;
    fscanf( fin, "%d", &n );
    robot.reserve( n );
    for( int i = 0; i < n; i++ ){
      int x, y;
      fscanf( fin, "%d%d", &x, &y );
      robot.emplace_back( x, y );

      start.x = std::min( start.x, x );
      start.y = std::min( start.y, y );
    }

    // folosim conventia din enunt pentru pozitia robotului
    for( Point &P : robot )
      P -= start;
  }

  std::vector<Poly> obstacles;
  { // citim obstacolele
    int m;
    fscanf( fin, "%d", &m );
    for( int i = 0; i < m; i++ ){
      int siz;
      fscanf( fin, "%d", &siz );
      obstacles.emplace_back();
      obstacles.back().reserve( siz );
      for( int i = 0; i < siz; i++ ){
        int x, y;
        fscanf( fin, "%d%d", &x, &y );
        obstacles.back().emplace_back( x, y );
      }

      obstacles.back() = enlarge_obstacle( obstacles.back(), robot );
    }
  }

  { // punem segmentele importante in dangerous[]
    for( const Poly& obs : obstacles ){
      int n = (int)obs.size();
      
      for( int i = 0; i < n; i++ ){
        dangerous.emplace_back( obs[i], obs[(i + 1) % n] );
        dangerous.emplace_back( obs[i], obs[(i + 2) % n] );
      }
    }
  }

  Point finish;
  fscanf( fin, "%d%d", &finish.x, &finish.y );

  // printf( "drum: (%d %d) -- (%d %d)\n", start.x, start.y, finish.x, finish.y );
  // hits_interior( Seg(start, finish) );
  // printf( "------------------\n" );

  int src = 0, dest = 1;
  Graph::points.push_back( start );
  Graph::points.push_back( finish );

  for( const Poly& obs : obstacles )
    for( Point P : obs )
      Graph::points.push_back( P );

  Graph::build();
  ftype ret = Graph::dijkstra( src, dest );

  if( ret < (ftype)(+INF) )
    fprintf( fout, "%.2lf\n", ret );
  else
    fprintf( fout, "-1\n" );

  fclose( fin );
  fclose( fout );
  return 0;
}