Language: C++

#include<iostream>
#include<complex>
#include<vector>
#include<set>
#include<algorithm>
#include<queue>
#include<map>

using namespace std;

typedef complex<long long> P;
typedef pair<long long,long long> Pi;
#define cvPPi(a) make_pair(a.real(),a.imag())

long long cross(const P &a, const P &b){return a.real() * b.imag() - a.imag() * b.real();}
long long dot(const P&a, const P&b){return a.real() * b.real() + a.imag() * b.imag();}
long long myabs(const P&a){return dot(a,a);}

bool online(P a, P b, P c){
  b-=a;
  c-=a;
  if( cross(b,c) == 0 ){
    if( dot(b,c) < 0 ) return false;
    if( myabs(b) < myabs(c) ) return false;
    return true;
  }
  return false;
}

namespace std{
  bool operator<(const P&a, const P&b){
    if( a.real() != b.real() ) return a.real() < b.real();
    return a.imag() < b.imag();
  }
}

struct compP{
  P base;
  compP(P t):base(t){}
  bool operator()(const P &a, const P &b){return myabs(a-base)<myabs(b-base);}
};

struct Segment{
  P a,b;
  set<Pi> S;
  vector<P> vp;
  Segment(){}
  Segment(const P &a, const P &b):a(a),b(b){S.insert(cvPPi(a));S.insert(cvPPi(b));vp.push_back(a);vp.push_back(b);}
  void insert(const P&a){
    if( S.find(cvPPi(a)) != S.end() ) return ;
    S.insert(cvPPi(a));
    vp.push_back(a);
  }
  void arrange(){ sort(vp.begin(),vp.end(),compP(a)); }
};

struct state{
  P pos;
  long long cost;
  state(){}
  state(P p, long long c):pos(p),cost(c){}
  bool operator>(const state &t)const{
    if(cost!=t.cost)return cost>t.cost;
    if(pos.imag()!=t.pos.imag())return pos.imag()>t.pos.imag();
    if(pos.real()!=t.pos.real())return pos.real()>t.pos.real();
    return false;
  }
};

const long long inf = 1LL<<62;
long long A[1010][1010];
P path[1010][1010];
map<P,set<P> > E;
set<pair<P,P> > proh;

void dijkstra(const P &s, const P &g){
  priority_queue<state,vector<state>,greater<state> > pq;

  for(int i = 0; i < 1010; ++i){
    for(int j = 0; j < 1010; ++j){
      A[i][j] = inf;
      path[i][j] = P(-1,-1);
    }
  }
  
  pq.push( state(s,0) );
  A[s.real()][s.imag()] = 0;

  while(!pq.empty()){
    state cur = pq.top(); pq.pop();
    for(set<P>::iterator it = E[cur.pos].begin(); it != E[cur.pos].end(); ++it){
      if( proh.find(make_pair(cur.pos,*it)) != proh.end() ) continue;
      state next(*it,myabs(*it-cur.pos)+cur.cost);
      if( A[next.pos.real()][next.pos.imag()] > next.cost ){
        A[next.pos.real()][next.pos.imag()] = next.cost;
        path[next.pos.real()][next.pos.imag()] = cur.pos;
        pq.push( next );
      }
    }
  }

  P cur = g;
  vector<P> res_path;
  while(cur.real()>=0){
    res_path.push_back(cur);
    cur = path[cur.real()][cur.imag()];
  }

  if( A[g.real()][g.imag()] == inf ){
    cout << -1 << endl;
  }else{
    for(int i = res_path.size()-1; i>=0; --i){
      cout << res_path[i].real() << ' ' << res_path[i].imag() << endl;
    }
    cout << 0 << endl;
  }
  
  return ;
}

void add_proh(P a, P b, P c, P x){
  assert(a!=x && b!=x && c!=x );
  // cout << a << ' ' << b << ' ' << c << ' ' << x << endl;
  
  a-=x;
  b-=x;
  c-=x;
  if( dot(c,a) == 0 ){
    // cout << "prohibited : " << a+x << "<-->" << b+x << endl; 
    proh.insert(make_pair(a+x,b+x));
    proh.insert(make_pair(b+x,a+x));
  }else if( dot(c,a) < 0 ){
    // cout << "prohibited : " << a+x << "  ->" << b+x << endl; 
    proh.insert(make_pair(a+x,b+x));
  }else{
    // cout << "prohibited : " << b+x << "<-  " << a+x << endl; 
    proh.insert(make_pair(b+x,a+x));
  }
}

int main()
{
  int n;
  while(cin>>n && n){
    P start, goal;
    bool isSign[n];
    vector<Segment> vs, nvs;

    cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
    for(int i = 0; i < n; ++i){
      P p1, p2;
      cin >> p1.real() >> p1.imag() >> p2.real() >> p2.imag();
      vs.push_back(Segment(p1,p2));
    }

    // check sign segment
    for(int i = 0; i < (int)vs.size(); ++i){
      P isp;
      int ise;
      int flag = 0;
      
      isSign[i] = false;
      for(int j = 0; j < 2; ++j){
        P x;
        if( j==0 ){x=vs[i].a;}
        if( j==1 ){x=vs[i].b;}
        for(int k = 0; k < (int)vs.size(); ++k){
          if( i == k ) continue;
          if( online(vs[k].a, vs[k].b, x) ){
            isp = x;
            ise = k;
            flag |= 1<<j;
          }
        }
      }
      if( flag != 3 && flag ){
        isSign[i] = true;
      }
    }

    // build graph
    for(int i = 0; i < (int)vs.size(); ++i){
      if( isSign[i] ) continue;
      for(int j = 0; j < 2; ++j){
        P x;
        if( j==0 ){x=vs[i].a;}
        if( j==1 ){x=vs[i].b;}
        for(int k = 0; k < (int)vs.size(); ++k){
          if( i == k || isSign[k] ) continue;
          if( online(vs[k].a, vs[k].b, x) ){
            vs[k].insert(x);
          }
        }
      }
    }

    E.clear();
    for(int i = 0; i < (int)vs.size(); ++i){
      if( isSign[i] ) continue;
      vs[i].arrange();
      for(int j = 0; j+1 < (int)vs[i].vp.size(); ++j){
        nvs.push_back(Segment(vs[i].vp[j],vs[i].vp[j+1]));
        E[vs[i].vp[j]].insert(vs[i].vp[j+1]);
        E[vs[i].vp[j+1]].insert(vs[i].vp[j]);
      }
    }
    
    // check sign segment and add prohibited rules
    proh.clear();
    for(int i = 0; i < (int)vs.size(); ++i){
      if( !isSign[i] ) continue;
      P isp;
      int ise;
      int flag = 0;
      for(int j = 0; j < 2; ++j){
        P x;
        if( j==0 ){x=vs[i].a;}
        if( j==1 ){x=vs[i].b;}
        for(int k = 0; k < (int)nvs.size(); ++k){
          if( i == k ) continue;
          if( online(nvs[k].a, nvs[k].b, x) ){
            isp = x;
            ise = k;
            flag |= 1<<j;
          }
        }
      }
      add_proh(nvs[ise].a,nvs[ise].b,flag==1?vs[i].b:vs[i].a,isp);
    }
    
    dijkstra(start,goal);
    
  }
  return 0;
}

Compiler output:
a.cc: In function 'void add_proh(P, P, P, P)':
a.cc:122:3: error: 'assert' was not declared in this scope
  122 |   assert(a!=x && b!=x && c!=x );
      |   ^~~~~~
a.cc:8:1: note: 'assert' is defined in header '<cassert>'; this is probably fixable by adding '#include <cassert>'
    7 | #include<map>
  +++ |+#include <cassert>
    8 | 
a.cc: In function 'int main()':
a.cc:149:9: error: no match for 'operator>>' (operand types are 'std::istream' {aka 'std::basic_istream<char>'} and 'long long int')
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |     ~~~ ^~ ~~~~~~~~~~~~
      |     |                |
      |     |                long long int
      |     std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/14/iostream:42,
                 from a.cc:1:
/usr/include/c++/14/istream:170:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  170 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:170:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'bool&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:174:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  174 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:174:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'short int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:177:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  177 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:177:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'short unsigned int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:181:7: note: candidate: 'std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]' (near match)
  181 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/14/istream:181:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:184:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  184 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:184:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'unsigned int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:188:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  188 |       operator>>(long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:188:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'long int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:192:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  192 |       operator>>(unsigned long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:192:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'long unsigned int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:199:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  199 |       operator>>(long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:199:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'long long int&' to an rvalue of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:203:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long long unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  203 |       operator>>(unsigned long long& __n)
      |       ^~~~~~~~
/usr/include/c++/14/istream:203:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'long long unsigned int&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:219:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(float&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  219 |       operator>>(float& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:219:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'float&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:223:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  223 |       operator>>(double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:223:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'double&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:227:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  227 |       operator>>(long double& __f)
      |       ^~~~~~~~
/usr/include/c++/14/istream:227:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: cannot bind non-const lvalue reference of type 'long double&' to a value of type 'long long int'
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
/usr/include/c++/14/istream:328:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  328 |       operator>>(void*& __p)
      |       ^~~~~~~~
/usr/include/c++/14/istream:328:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: invalid conversion from 'long long int' to 'void*' [-fpermissive]
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |            ~~~~~~~~~~^~
      |                      |
      |                      long long int
a.cc:149:22: error: cannot bind rvalue '(void*)start.std::complex<long long int>::real()' to 'void*&'
/usr/include/c++/14/istream:122:7: note: candidate: 'std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(__istream_type& (*)(__istream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]' (near match)
  122 |       operator>>(__istream_type& (*__pf)(__istream_type&))
      |       ^~~~~~~~
/usr/include/c++/14/istream:122:7: note:   conversion of argument 1 would be ill-formed:
a.cc:149:22: error: invalid conversion from 'long long int' to 'std::basic_istream<char>::__istream_type& (*)(std::basic_istream<char>::__istream_type&)' {aka 'std::basic_istream<char>& (*)(std::basic_istream<char>&)'} [-fpermissive]
  149 |     cin >> start.real() >> start.imag() >> goal.real() >> goal.imag();
      |