2007台北大会 問題E

ACM/ICPC

台北大会で出た問題のひとつで、うちのチームがデバッグしきれずに通せなかった問題を紹介します。たぶん面白い問題だと思います。

ネタバレは含んでいませんが、台北大会の問題セットで練習しようと思っている人もいると思うので→


二次元平面上に線分がn本あります。各線分はx軸かy軸に平行です。これらの線分を道路だと思ってください。道路同士が直角に交差しているところは交差点になります。

さて、このいくつかの道路の上でカーレースを開こうと思います。レースのコースは次のような条件を満たさなければなりません:

  1. ある交差点から始まって、最後にその交差点に戻ってくるような経路であること、
  2. コース上でのUターンは許されない、
  3. コース中での右折・左折の回数は合わせてT回以下でなければならない。

これらの条件を満たすようなコースの中で、一番長いものの長さを計算するプログラムを作成しなさい。なお、そのようなコースがない場合は解無しと出力しなさい。

ただし、以下の制約条件を仮定してよいです。

  • 0 <= n <= 20,
  • 0 <= T <= 2147483647,
  • 線分の端点の座標は整数で、x,y座標ともに-2147483648〜2147483647の範囲に収まる。


たとえば、(0,0)-(1,0)-(1,1)-(0,1)-(0,0)のような四角形上の道路で、T=6の場合を考えると、道路を1周するようなコースが最長になります。T=7の場合は、道路を2周するようなコースです。