cafelier@SRM

Codeforces #13 B

Codeforces | 09:30 |

幾何の問題はTopcoderだとそんなに見ないので、Codeforces #13 の B 問題を借りて、どんな風に考えながら解いているかメモしてみる。

• 『3本の線分が与えられます。アルファベットのAの形になっているかどうか判定してね。Aになっていると見なす条件は』
  1. 3本のうち2本が（"first" と "second" と仮に呼ぶことにしよう）、端点を共有している
  2. 残りの1本("third")は、first上の一点とsecond上の一点を結線分である
  3. thirdは、firstやsecondを、バランスよさめにわける。具体的には、1:4 以内の比で分割する
• 座標はintに収まる程度の整数。10000テストケース。

• とりあえずソース

#include <iostream>
#include <algorithm>
#include <complex>
#include <cmath>
#include <cstdio>
using namespace std;
static const double EPS = 1e-9;

typedef complex<double> point;
struct line { point p, q; };

double point_on_line(const point& p, const line& a)
{
   // regard "a" as "x-axis"
   point f = (p-a.p) / (a.q-a.p);
   // return p's "x-coordinate" if it is on "x-axis"
   return abs(f.imag())<EPS ? f.real() : -1;
}

bool isA(const line& a, const line& b, const line& c)
{
   // "first" and "second" have common endpoint
   if( a.p != b.p )
      return false;

   // the angle between them is in 0 to 90
   double ag = abs( arg( (a.q-a.p)/(b.q-b.p) ) );
   if( ag > atan2(1.0,0.0)+EPS )
      return false;

   // "third" connects two points on "first" and "second" in >1:4
   double p1 = point_on_line(c.p, a);
   double p2 = point_on_line(c.q, b);
   if( p1<0.2-EPS || 0.8+EPS<p1 )
      return false;
   if( p2<0.2-EPS || 0.8+EPS<p2 )
      return false;

   return true;
}

bool tryAllSwap(line a, line b, line c)
{
   // try all endpoint ordering
   for(int i=0; i<8; ++i)
   {
      if( isA(a,b,c) )
         return true;
      if(i%1==0) swap(a.p, a.q);
      if(i%2==0) swap(b.p, b.q);
      if(i%4==0) swap(c.p, c.q);
   }
   return false;
}

bool tryAllPerm( line ls[3] )
{
   // try all permutation of "first", "second", and "third"
   int ix[] = {0,1,2};
   do
      if( tryAllSwap( ls[ix[0]], ls[ix[1]], ls[ix[2]] ) )
         return true;
   while( next_permutation(&ix[0], &ix[3]) );
   return false;
}

int main()
{
   int t; { cin >> t; }

   while( t --> 0 )
   {
      line ls[3];
      for(int i=0; i<3; ++i)
      {
         double x1, y1, x2, y2;
         scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); //cinだと入力だけで800msかかる…
         ls[i].p = point(x1,y1);
         ls[i].q = point(x2,y2);
      }
      cout << (tryAllPerm(ls) ? "YES" : "NO") << endl;
   }
}

• まったく幾何に限らないですが
• 僕がブルートフォースが好きという時は、上記のようなコードが念頭にありました。
  • tsukuno さんの考えはどうかわかりませんが

bool tryAllSwap(line a, line b, line c)
bool tryAllPerm( line ls[3] )

• この辺ですね。
  • 「まず端点を共有している線分ペアを探して、それをfirstとsecondとして、しかも共有端点が先に来るように線分の表現を正規化して、それから A になる条件 2 と 3 をチェック」
  • のようなコードは、
  • タイムリミットが厳しい時でなければ、「美しくない」と思う。
    • たとえそちらの方が短くても、そう思う気がする。
• どれが "first", "second", "third" になるか 3! 全部試す
• first/secondのどっちの端点が共有端点になるか、thirdのどっちの端点がfirst/secondのどっちに載る方になるか、
• 全部試す。これ。

• 幾何の話をしよう。
• 幾何と見ればとりあえず「complex厨になる」

#include <complex>
typedef complex<double> point;

• とりあえず二次元の話は全部複素平面で考える。
  • abs(p) で z と原点の距離が取れます
  • arg(p) で原点からpを結ぶ線とx軸の角度が取れます
  • q += p で、qを、原点からpに向かうベクトルの分平行移動できます
  • q *= polar(1, theta) で、q を原点中心に角度 theta 回転できます
  • q /= p で、原点からpに向かうベクトルをx軸と思って軸を取り直したときのqの新しい座標が求まります
• などなど。便利。

• 回転と平行移動を駆使する
• 『3点p,q,rが与えられます。rが線分pq上にあるかどうか判定して下さい』
• という問題を考えてみましょう。
  • そのままやると、pq を結ぶ直線の式を y=ax+b の形で解いて、rがこれに当てはまるか…
  • みたいになことになって大変だったりします。

• そこで平行移動+回転する

• p,q,r の全部から p を引くと 0, q-p, r-p になりますが、
• これはつまり、「pが原点に来るように図形全体を平行移動した」ことになります。
• さらに、ここで全部を q-p で割ると 0, 1, (r-p)/(q-p) になりますが、
• これはつまり、「qがx軸上の点(1,0)に来るように全体を回転＆拡縮した」ことになります。

• で、平行移動や回転や拡大縮小では「点が線分の上にあるかどうか」はかわらないので
• この状態で、「rの移動後の点が、線分(pの移動後)-(qの移動後)に乗っているかどうか？」を判定すれば答えが出ます。
  • pが原点に行っていて
  • qが(1,0)に行っているので、
  • この判定は簡単ですね。rの移動後が、「y座標が0でx座標が0と1の間」なら線分に乗っています。
• というのが

double point_on_line(const point& p, const line& a)

• この関数。乗ってる場合にrがpqを何対何に分けてるか？も回転等々で変わらないので、その値もついでに返してます。

補足など

• 謝辞： 僕の記憶が正しければ、こういう「原点に移動したり回転したりすると問題がとても簡単になる（ことがある）」という考え方は gusmachine さんに教わった記憶。感謝感謝。
• complex厨になったり何でも無造作に割り算で回転したりするやり方の欠点として「誤差に注意しないとヤバい」というのがあります。
  • さっきの線分に乗ってるか判定なら、ベクトルの外積や ccw を使えば、整数座標の場合すべて整数のまま計算を終えることができて、誤差に煩わされずに安心。
  • なので、この問題については、ベストの解としては、そちらの方がオススメです。
  • もっと複雑なケースで、汎用的に使える考え方として、便利なんじゃないかなーと思います＞回転移動アタック