以下のように平面上に13点がある。ここから4個ずつ3組の点を選び(四角形になる)，同じ大きさ，同じ形になるようにするにはどうすれば良いか。
四角形は凸(Convex)になるようにする。
先週4問出題されたので，今週は休みだと思っていたら休みじゃなかった。油断した。
直感的に以下のような分類を考えたが，いきなりの挫折。こんな簡単じゃないよな。
長さ5がキーになりそうなので，長さ5の線を選び出してみた。結構ある。
これをジーッと見つめ続ける。以下のような三角形が浮かんできた。
ここまで来ながらもう一つを見逃してしまったため頭で解くのは失敗した。以下の緑の線に気づけば解までたどり着けたかも知れない。
その後，角度の違う次の図を眺めたけどダメだった。
ということでプログラムを作って解いてしまった。
13点から4点を選んで四角形を作成すると，凸四角形は3656件。
これを虱潰しに調べると，48,867,324,416回(36563)になってしまうので，もっと絞り込む。4辺の長さが同じものを絞り込んだら多いもので120件になった。
これなら虱潰しにしても172万(1203)回。
但し4辺の長さだけだと以下のような組合せを出力してしまうので，面積も考慮する。
プログラムの出力した解を見てみると，「あー，ショックー，何でこれが判らなかったのかー」って気持ちになる。
プログラムは数字の割り当て問題をちょっと改良し，13点から4点を虱潰す以下のコードになる。
YesNo used[1+13];
for( int a=1; a<= 13; a++) {
used[a] = YES;
for( int b=1; b<= 13; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=1; c<= 13; c++) {
if( used[c]) continue;
used[c] = YES;
for( int d=1; d<= 13; d++) {
if( used[d]) continue;
if( 点(a,b,c,d)が凸四角形の場合) {
四角形の辺長,面積を求め,(a,b,c,d)を記録する
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
記録した四角形をsortし，同じ辺長，同じ面積のものを集める。
重複を除去する。// (a,b,c,d)と(b,c,d,a)が含まれるので
同じ辺長，同じ面積の中から全て別の点になる組合せを調べる。
四角形ABCDが凸かどうかの判定は，
線ACに対し点B,Dが異なる側にあり且つ線BDに対し点A,Cが異なる側にある
を用いた。
判定のための関数は以下の通り。
直線A(ax,ay)-B(bx,by)に対し点C(cx,cy),D(dx,dy)が同じ側にあれば1を，反対側にあれば-1を，それ以外の場合(AB上にCが乗ってしまう場合など)0を返す。
int checkpoint( int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy)
{
int dbx = bx - ax;
int dby = by - ay;
int dcx = cx - ax;
int dcy = cy - ay;
int ddx = dx - ax;
int ddy = dy - ay;
int dc = dbx*dcy - dby*dcx;
int dd = dbx*ddy - dby*ddx;
if( dc > 0 && dd > 0) return 1;
else if( dc > 0 && dd < 0) return -1;
else if( dc < 0 && dd > 0) return -1;
else return 0;
}
int isConvex( int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy)
{
return checkpoint( ax, ay, cx, cy, bx, by, dx, dy) < 0 && checkpoint( bx, by, dx, dy, ax, ay, cx, cy) < 0;
}
面積の計算には以下の関数を使用した。実際の面積はtri1,tri2を1/2しなければならないが，比較のためだけに利用するので，そのままにしてある(小数が出たら困る)。
int calcmenseki2( int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy)
{
int dx1 = bx - ax;
int dy1 = by - ay;
int dx2 = cx - ax;
int dy2 = cy - ay;
int dx3 = dx - ax;
int dy3 = dy - ay;
int tri1 = dx1*dy2 - dy1*dx2;
int tri2 = dx2*dy3 - dy2*dx3;
return abs(tri1) + abs(tri2);
}
解速度
即