fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cmath>
  6. #include <queue>
  7. #include <iomanip>
  8. using namespace std;
  9.  
  10. ifstream F("robot.in");
  11. ofstream G("robot.out");
  12.  
  13. const double eps = 1e-9;
  14. const int infi = 1<<30;
  15. const int debuging = 0;
  16.  
  17. #define x first
  18. #define y second
  19.  
  20. typedef pair<int,int> pi;
  21. typedef pair<double,double> pd;
  22.  
  23. pi finish;
  24. vector<pi> robot;
  25. vector< vector<pi> > obstacle;
  26.  
  27. int ecu(pi A,pi B,pi C)
  28. {
  29.     int a = A.y - B.y;
  30.     int b = B.x - A.x;
  31.     int c = - A.y * B.x + B.y * A.x;
  32.     int d = a * C.x + b * C.y + c;
  33.     return d > 0 ? 1 : ( d < 0 ? -1 : 0 );
  34. }
  35.  
  36. int segment(pi A,pi B,pi C)
  37. {
  38.     if ( ecu(A,B,C) ) return 0;
  39.     if ( min(A.x,B.x) > C.x || C.x > max(A.x,B.x) ) return 0;
  40.     if ( min(A.y,B.y) > C.y || C.y > max(A.y,B.y) ) return 0;
  41.     return 1;
  42. }
  43.  
  44. void print_vector(vector<pi> V)
  45. {
  46.     if ( debuging == 0 ) return;
  47.     G<<"debug: ";
  48.     for (vector<pi>::iterator it=V.begin();it!=V.end();++it)
  49.         G<<'('<<it->x<<","<<it->y<<") ";
  50.     G<<"\n";
  51. }
  52.  
  53. void cprint_vector(vector<pi> V)
  54. {
  55.     if ( debuging == 0 ) return;
  56.     cout<<"debug: ";
  57.     for (vector<pi>::iterator it=V.begin();it!=V.end();++it)
  58.         cout<<'('<<it->x<<","<<it->y<<") ";
  59.     cout<<"\n";
  60. }
  61.  
  62. void print_array(double A[],int sz)
  63. {
  64.     if ( debuging == 0 ) return;
  65.     G<<"debug: ";
  66.     for (int i=0;i<sz;++i)
  67.     {
  68.         if ( max(A[i]-infi,infi-A[i]) < eps ) G<<"infi "; else
  69.         G<<fixed<<setprecision(2)<<A[i]<<" ";
  70.     }
  71.     G<<"\n";
  72. }
  73.  
  74. void read()
  75. {
  76.     int N=0,M=0;
  77.     F>>N;
  78.     for (int i=1,x,y;i<=N;++i)
  79.     {
  80.         F>>x>>y;
  81.         robot.push_back( make_pair(x,y) );
  82.     }
  83.     F>>M;
  84.     for (int i=1;i<=M;++i)
  85.     {
  86.         vector<pi> act;
  87.         F>>N;
  88.         for (int j=1,x,y;j<=N;++j)
  89.         {
  90.             F>>x>>y;
  91.             act.push_back( make_pair(x,y) );
  92.         }
  93.         obstacle.push_back( act );
  94.     }
  95.     F>>finish.x>>finish.y;
  96. }
  97.  
  98. pi trans(pi a,pi t,pi o)
  99. {
  100.     return make_pair( a.x - o.x + t.x , a.y - o.y + t.y );
  101. }
  102.  
  103. void convex_hull(vector<pi>& A)
  104. {
  105.     sort(A.begin(),A.end());
  106.     A.erase( unique( A.begin(),A.end() ) , A.end() );
  107.     vector<pi> out;
  108.     vector<pi> stack;
  109.     int N = A.size();
  110.  
  111.     for (int i=0;i<N;++i)
  112.         if ( ecu(A[0],A[N-1],A[i]) >= 0 )
  113.         {
  114.             if ( stack.size() > 1 )
  115.                 while ( ecu( stack[stack.size()-2] , A[i] , stack[stack.size()-1] ) <= 0 )
  116.                 {
  117.                     stack.pop_back();
  118.                     if ( stack.size() < 2 ) break;
  119.                 }
  120.             stack.push_back(A[i]);
  121.             cprint_vector(stack);
  122.         }
  123.     while ( !stack.empty() )
  124.     {
  125.         stack.pop_back();
  126.         if ( !stack.empty() )
  127.             out.push_back( stack.back() );
  128.     }
  129.  
  130.     for (int i=N-1;i>=0;--i)
  131.         if ( ecu(A[N-1],A[0],A[i]) >= 0 )
  132.         {
  133.             if ( stack.size() > 1 )
  134.                 while ( ecu( stack[stack.size()-2] , A[i] , stack[stack.size()-1] ) <= 0 )
  135.                 {
  136.                     stack.pop_back();
  137.                     if ( stack.size() < 2 ) break;
  138.                 }
  139.             stack.push_back(A[i]);
  140.             if ( debuging ) cprint_vector(stack);
  141.         }
  142.     while ( !stack.empty() )
  143.     {
  144.         stack.pop_back();
  145.         if ( !stack.empty() )
  146.             out.push_back( stack.back() );
  147.     }
  148.  
  149.     A = out;
  150. }
  151.  
  152. void expand()
  153. {
  154.     sort(robot.begin(),robot.end());
  155.     for (size_t i=0;i<obstacle.size();++i)
  156.     {
  157.         int size = obstacle[i].size();
  158.         for (int j=0;j<size;++j)
  159.             for (size_t k=0;k<robot.size();++k)
  160.                 obstacle[i].push_back( trans(obstacle[i][j],robot[0],robot[k]) );
  161.         convex_hull( obstacle[i] );
  162.         if ( debuging ) print_vector( obstacle[i] );
  163.     }
  164. }
  165.  
  166. void placef()
  167. {
  168.     int miny = robot[0].y;
  169.     for (size_t i=1;i<robot.size();++i)
  170.         miny = min(miny,robot[i].y);
  171.     finish.y += robot[0].y-miny;
  172. }
  173.  
  174. double dist(pi A,pi B)
  175. {
  176.     return sqrt( (A.x-B.x) * (A.x-B.x) + (A.y-B.y) * (A.y-B.y) );
  177. }
  178.  
  179. int next(int i,int s)
  180. {
  181.     return i+1 < s ? i+1 : 0;
  182. }
  183.  
  184. int cross(pi a,pi b)
  185. {
  186.     return a.x * b.y - a.y * b.x;
  187. }
  188.  
  189. int area(vector<pi> v)
  190. {
  191.     int out = 0;
  192.     for (size_t i=0;i<v.size()-1;++i)
  193.         out += cross(v[i],v[i+1]);
  194.     out = max(out,-out);
  195.     return out;
  196. }
  197.  
  198. int tarea(pi A,pi B,pi C)
  199. {
  200.     int out = cross(A,B) + cross(B,C) + cross(C,A);
  201.     out = max(out,-out);
  202.     return out;
  203. }
  204.  
  205. int parea(vector<pi> v,pi a)
  206. {
  207.     int out = 0;
  208.     for (size_t i=0;i<v.size()-1;++i)
  209.         out += tarea(v[i],v[i+1],a);
  210.     return out;
  211. }
  212.  
  213. pd internow;
  214.  
  215. int int2(pi A,pi B,pi C,pi D)
  216. {
  217.     double a1 = A.y - B.y;
  218.     double b1 = B.x - A.x;
  219.     double c1 = - A.y * B.x + B.y * A.x;
  220.  
  221.     double a2 = C.y - D.y;
  222.     double b2 = D.x - C.x;
  223.     double c2 = - C.y * D.x + D.y * C.x;
  224.  
  225.     double d = a1*b2 - b1*a2;
  226.     if ( d == 0 )
  227.         return 0;
  228.     else
  229.     {
  230.         internow = make_pair( (b2*c1-b1*c2)/d , (a1*c2-a2*c1)/d );
  231.         return ecu(C,B,A)*ecu(D,B,A)<=0 && ecu(A,C,D)*ecu(B,C,D)<=0;
  232.     }
  233. }
  234.  
  235. bool intersection(pi A,pi B,vector<pi> V)
  236. {
  237.     int N = V.size();
  238.     V.push_back(V[0]);
  239.  
  240.     for (int i=0;i<N;++i)
  241.         if ( ecu(A,V[i],V[i+1]) == 0 && ecu(B,V[i],V[i+1]) == 0 )
  242.             return 0;
  243.  
  244.     int a=0,b=0;
  245.     for (int i=0;i<N;++i)
  246.     {
  247.         if ( segment(V[i],V[i+1],A) ) a = 1;
  248.         if ( segment(V[i],V[i+1],B) ) b = 1;
  249.     }
  250.  
  251.     if ( a && b ) return 1;
  252.  
  253.     int area_v = area(V);
  254.     int area_a = parea(V,A);
  255.     int area_b = parea(V,B);
  256.  
  257.     if ( area_v == area_a && a == 0 ) return 1;
  258.     if ( area_v == area_b && b == 0 ) return 1;
  259.  
  260.     vector<pd> inter;
  261.     for (int i=0;i<N;++i)
  262.         if ( int2(A,B,V[i],V[i+1]) )
  263.             inter.push_back( internow );
  264.  
  265.     sort(inter.begin(),inter.end());
  266.     inter.erase(unique(inter.begin(),inter.end()),inter.end());
  267.  
  268.     return inter.size() > 1;
  269. }
  270.  
  271. double distancee(pi A,pi B)
  272. {
  273.     if ( A == B ) return 0;
  274.     double out = dist(A,B);
  275.     for (vector< vector<pi> >::iterator vect=obstacle.begin();vect!=obstacle.end();++vect)
  276.         if ( intersection(A,B,*vect) )
  277.             return infi;
  278.     return out;
  279. }
  280.  
  281. void solve()
  282. {
  283.     vector<pi> points;
  284.     points.push_back( robot[0] );
  285.     for (vector< vector<pi> >::iterator vect=obstacle.begin();vect!=obstacle.end();++vect)
  286.         for (vector<pi>::iterator it=vect->begin();it!=vect->end();++it)
  287.             points.push_back(*it);
  288.     points.push_back( finish );
  289.  
  290.     int N = points.size();
  291.     double cost[N+10][N+10];
  292.     for (int i=0;i<N;++i)
  293.         for (int j=0;j<N;++j)
  294.             cost[i][j] = distancee(points[i],points[j]);
  295.  
  296.     for (int i=0;i<N;++i)
  297.         print_array( cost[i],N );
  298.  
  299.     double d[N+10];
  300.     for (int i=0;i<N;++i)
  301.         d[i] = infi;
  302.  
  303.     d[0] = 0;
  304.     queue<int> Q;
  305.     Q.push(0);
  306.  
  307.     if ( debuging ) G<<"\n";
  308.  
  309.     while ( Q.size() )
  310.     {
  311.         int node = Q.front();
  312.         Q.pop();
  313.  
  314.         for (int i=0;i<N;++i)
  315.             if ( d[node] + cost[node][i] < d[i] - eps )
  316.             {
  317.                 Q.push( i );
  318.                 d[i] = d[node] + cost[node][i];
  319.             }
  320.         print_array(d,N);
  321.     }
  322.  
  323.     G<<fixed<<setprecision(3)<<d[N-1]<<'\n';
  324. }
  325.  
  326. int main()
  327. {
  328.     read();
  329.     expand();
  330.     placef();
  331.     solve();
  332. }
  333.  
Runtime error #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N8ezqt
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!