Language: C++


#include <bits/stdc++.h>

// -----------------------------------------------------------------------
// commonly used template
#if !defined commonly_used_template
#define commonly_used_template

#define REP(i,a,b) for(int i=a; i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS (1e-7)
int const INF = 1<<29;

#endif
// -----------------------------------------------------------------------

using namespace std;

#define fi first
#define se second

// ------------------------------------------------------
// common graph
#if !defined common_graph
#define common_graph

struct Edge { int to; double cost; };
typedef std::vector<Edge> Edges;
typedef std::vector<Edges> Graph;

#endif
// ------------------------------------------------------

// -----------------------------------------------------------------------
// common geometry
#if !defined common_geometry
#define common_geometry

typedef complex<double> P;
typedef complex<int> IntP;

bool is_equal(P const& a, P const& b) {
  if(abs(a-b) < EPS) return true;
  return false;
}

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

double dot(P const& a, P const& b) {
  return real(conj(a)*b);
}

double cross(P const& a, P const& b) {
  return imag(conj(a)*b);
}

struct Circle
{
  P p; double r;
  Circle(P const& p, double r) : p(p), r(r) { }
};

struct Line : public vector<P>
{
  Line(P const& a, P const& b) {
    push_back(a), push_back(b);
  }
  double length() { return abs((*this)[0] - (*this)[1]); }
  P vectorize() { return (*this)[1] - (*this)[0]; }
};
ostream& operator << (ostream& ost, Line const& ln) {
  return ost << "{" << ln[0] << ", " << ln[1] << "}";
}

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if(cross(b, c) > 0) return +1;
  if(cross(b, c) < 0) return -1;
  if(dot(b, c) < 0) return +2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

bool is_cross(Line const& s, Line const& t) {
  return ( ccw(s[0], s[1], t[0]) * ccw(s[0], s[1], t[1]) < EPS )
    && ( ccw(t[0], t[1], s[0]) * ccw(t[0], t[1], s[1]) < EPS );
}

P crosspoint(Line const& a, Line const& b) {
  double k = cross(a[1]-a[0], b[1]-b[0]);
  double t = cross(a[1]-a[0], a[1]-b[0]);
  if(abs(k) < EPS && abs(t) < EPS) return b[0];
  return b[0] + t/k * (b[1]-b[0]);
}

#endif
// -----------------------------------------------------------------------

set<int> is_signsw;

int id_size;
vector<int> deg;
map<int, P> to_point;
map<P, int> to_id;

typedef pair<int, bool> PathNode;
vector<int> prev_path;
vector<double> dist;

Graph g;


double dijkstra(Graph const& g, int S, int T) {
  
  prev_path.resize(id_size);
  prev_path[S] = -1;
  
  dist.resize(id_size);
  
  rep(i, dist.size()) dist[i] = INF;
  dist[S] = 0.;
  
  typedef pair<double, int> Pdi;
  
  priority_queue<Pdi> pq;
  pq.push(Pdi(dist[S], S));
  while(!pq.empty()) {
    Pdi pdi = pq.top(); pq.pop();
    double const cost = -pdi.fi;
    int pos = pdi.se;
    
    if(pos == T) return cost;
    
    rep(i, g[pos].size()) {
      Edge const& e = g[pos][i];
      if(e.to == -1) { continue; } // 通過不可のため削除された道
      if(dist[e.to] <= cost+e.to) { continue; }
      dist[e.to] = cost+e.to;
      pq.push(Pdi(-dist[e.to], e.to));
      prev_path[e.to] = pos;
    }
  }
  
  return INF;
}

vector<Line> subdivide_lines(vector<Line> const& lines)
{
  vector<Line> ret;
  rep(i, lines.size()) {
    set<Line> st;
    Line const& me = lines[i];

    vector<P> vs;
    vs.push_back(me[0]); vs.push_back(me[1]);
    rep(j, lines.size()) {
      if(i == j) { continue; }
      bool crossed = 0;
      Line const& tg = lines[j];
      if(is_cross(me, tg)) {
        P cp = crosspoint(me, tg);
        if(is_equal(me[0], cp) || is_equal(me[1], cp)) { continue; } // 交点が自分の線分の端点の場合を除外
        crossed = 1;
        vs.push_back(crosspoint(me, tg));
      }
    }
    
    sort(vs.begin(), vs.end());

    rep(i, (int)vs.size()-1) {
      st.insert(Line(vs[i], vs[i+1]));
    }

    for(auto i : st) {
      ret.push_back(i);
    }

  }
  
  return ret;
}

void init_global()
{
  is_signsw.clear();
  to_point.clear();
  to_id.clear();
  g.clear();
  deg.clear();
  prev_path.clear();
  dist.clear();
}

int main()
{
  int N;
  int xs, ys, xg, yg;
  while(cin >> N && N) {
    init_global();
    
    set<P> intersections;
    cin >> xs >> ys >> xg >> yg;
    intersections.insert(P(xs, ys)); intersections.insert(P(xg, yg));
    vector<Line> raw_lines;
    rep(i, N) {
      int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
      intersections.insert(P(x1, y1));
      intersections.insert(P(x2, y2));
      raw_lines.push_back(Line(P(x1,y1), P(x2,y2)));
    }
    
    vector<Line> lines = subdivide_lines(raw_lines);

    typedef pair<int, int> Pii;
    set<Pii> st; // 新規ノード追加用
    
    id_size = 0;
    rep(i, lines.size()) {
      Line& ln = lines[i];
      rep(k, 2) {
        Pii LNK = Pii((int)ln[k].real(), (int)ln[k].imag());
        if(!st.count(LNK)) {
          to_point[id_size] = ln[k];
          to_id[ln[k]] = id_size;
          id_size ++;
          g.resize(id_size);
          deg.resize(id_size);
          st.insert(LNK);
        }
      }
      int s = to_id[ln[0]], t = to_id[ln[1]];
      g[s].push_back((Edge){t, ln.length()});
      g[t].push_back((Edge){s, ln.length()});
      deg[s] ++, deg[t] ++;
    }
    
    rep(i, id_size) {
      rep(j, g[i].size()) {
        Edge const& e = g[i][j];
        if(e.to == -1) { continue; }
        if(deg[e.to] != 1) { continue; }

        // 標識の分岐点を登録
        is_signsw.insert(i);
        
        rep(k, g[i].size()) {
          if(f.to == -1) { continue; }
          Edge const& f = g[i][k];
          if(e.to == f.to) { continue; }
          
          P sign_end = to_point[e.to];
          P swpoint = to_point[i];
          P come = to_point[f.to];
          sign_end -= swpoint, come = swpoint - come;

          if(dot(sign_end, come) > -EPS) {
            // come -> 標識の分岐点 の道を削除する
            rep(ii, g[f.to].size()) {
              if(g[f.to][ii].to == i) { g[f.to][ii].to = -1; break; }
            }
          }
        }
      }
    }
    
    int S = to_id[P(xs, ys)], T = to_id[P(xg, yg)];

    // dijkstra
    int ans = dijkstra(g, S, T);
    if(ans == INF) {
      cout << -1 << endl;
    }
    else {
      vector<pair<int, int> > path;
      int now = T;
      for(; now!=S; now = prev_path[now]) {
        if(is_signsw.count(now)) { continue; }
        P& p = to_point[now];
        if(!intersections.count(p)) { continue; }
        path.push_back(make_pair(p.real(), p.imag()));
      }
      path.push_back(make_pair(xs, ys));
      reverse(path.begin(), path.end());
      rep(i, path.size()) {
        cout << path[i].fi << " " << path[i].se << endl;
      }
      cout << 0 << endl;
    }
    
  }
  
  return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:262:14: error: 'f' was not declared in this scope
  262 |           if(f.to == -1) { continue; }
      |              ^