AOJ 1279 : Geometric Map

問題リンク : Geometric Map | Aizu Online Judge

問題概要：
n本の線分が与えられる　（n <= 200）
線分は必ず１本以上の他の線分と端点で交差している
線分の両端が別の線分の端点と交差しているならばそれは道である
線分の片方だけが別の線分の端点と交差しているならばそれは標識である
標識は交差している線分との角度が小さい方から大きい方へしか進めない亊を意味する
もし標識が線分と垂直に交わっているならばその線分は通る亊ができない
線分上に二点、スタート地点とゴール地点が与えられる
その二点を結ぶ最短経路の通る交点を順に出力せよ（最後に０も出力する）
ゴールに到達できない場合は-1を出力せよ

解法：
線分アレンジメントしてdijkstraを行った
最初にその線分が道路なのか標識なのかを判別する
これはループで全ての線分に対して交差判定を行いその線分の両端点がどれか別の線分と交差しているかどうかで判定する
次に線分アレンジメントしてグラフを構築する
後はdijkstraで経路を記録しつつ最短経路を求める
今いる点から次の点に移動する際に、今いる点と次に行く点からなる線分が標識と交差していないか、交差しているのであれば通行可能かどうかを判断する

コード:

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define EPS (1e-8)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define MAX 300
#define all(n) (n).begin(),(n).end()

using namespace std;

//幾何ライブラリ

struct Edge
{
  int from,to;
  double cost;
  Edge(int from=inf,int to=inf,double cost=inf):from(from),to(to),cost(cost){}
  bool operator < (const Edge& a)const
  {
    return cost < a.cost;
  }
};


struct Pox
{
  int cur;
  double cost;
  Pox(int cur=inf,double cost=inf):cur(cur),cost(cost){}
  bool operator < (const Pox &a)const
  {
    return cost > a.cost;
  }
};

int n;
Segment seg[MAX];
vector<Segment> road,sign;

double getArg(Point A,Point B,Point C)
{
  double a = abs(B-C);
  double b = abs(A-C);
  double c = abs(A-B);
  return acos((b*b+c*c-a*a)/(2.0*b*c));
}

bool check(Segment s)
{
  rep(i,sign.size())
    if(intersectSS(sign[i],s))
      {
	Point a = crosspoint(sign[i],s);
	Point b = s.p1;
	Point c = (a==sign[i].p1?sign[i].p2:sign[i].p1);
	double arg = getArg(a,b,c);
	if(equals(arg,toRad(90.0)))return false;
	if(arg > toRad(90.0))return false;
      }
  return true;
}

void compute()
{
  vector<Point> ps;
  vector<vector<Edge> > g = segmentArrangement(road,ps);



  int size = ps.size();
  double mincost[size];
  int path[size];
  rep(i,size)mincost[i] = path[i] = inf;

  int s,t;
  s = t = -1;
  rep(i,size)
    if(ps[i] == start)s = i;
    else if(ps[i] == goal)t = i;
  assert(s != -1 && t != -1);

  mincost[s] = 0;
  priority_queue<Pox> Q;
  Q.push(Pox(s,0));

  while(!Q.empty())
    {
      Pox pox = Q.top(); Q.pop();

      if(pox.cur == t)
	{
	  vector<Point> ans;
	  for(int p=t;;p=path[p])
	    {
	      ans.push_back(ps[p]);
	      if(p == s)break;
	    }
	  reverse(all(ans));
	  rep(i,ans.size())
	    printf("%.0lf %.0lf\n",ans[i].x,ans[i].y);
	  puts("0");
	  return;
	}

      rep(i,g[pox.cur].size())
	{
	  int to = g[pox.cur][i].to;
	  double cost = g[pox.cur][i].cost;
	  Segment s = Segment(ps[pox.cur],ps[to]);
	  if(!check(s))continue;

	  if(mincost[to] > pox.cost + cost)
	    {
	      mincost[to] = pox.cost + cost;
	      path[to] = pox.cur;
	      Q.push(Pox(to,mincost[to]));
	    }
	}

    }
  cout << -1 << endl;
}

void split_seg()
{
  road.clear();
  sign.clear();

  rep(i,n)
    {
      bool L,R;
      L = R = false;
      rep(j,n)
	{
	  if(i == j)continue;
	  if(intersectSP(seg[j],seg[i].p1))L = true;
	  if(intersectSP(seg[j],seg[i].p2))R = true;
	  if(L&R)break;
	}
      if(L&R)road.push_back(seg[i]);
      else   sign.push_back(seg[i]);
      //cout << "seg : " << seg[i] << " is " << (L&R?"road":"sign") << endl;
    }

}

int main()
{
  while(scanf("%d",&n),n)
    {
      scanf("%lf %lf",&start.x,&start.y);
      scanf("%lf %lf",&goal.x ,&goal.y);
      rep(i,n)
	{
	  double x1,y1,x2,y2;
	  scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	  seg[i] = Segment(Point(x1,y1),Point(x2,y2));
	}	

      split_seg();
	
      compute();

    }
  return 0;
}