朝日新聞2004年7月24日パズルパーク解答

プログラムの実行結果は以下の通り。

Convex:3656
発見
[330]a: 1,b: 3,c: 8,d: 9, bits: 185, d1:10,d2:20,d3:25,d4:25,35
[332]a: 2,b: 6,c: 7,d:11, bits: 462, d1:10,d2:20,d3:25,d4:25,35
[333]a: 4,b: 5,c:10,d:12, bits: a18, d1:10,d2:20,d3:25,d4:25,35

図示すると以下の通り。

プログラムのソースは以下の通り。

#include "puzutl.h"

struct xy { // 図の点
  int x;
  int y;
} data[] = {
  { 0, 0}, // 点の番号をINDEXで使いたいので最初はDUMMY
  { 1, 8}, // 1
  { 6, 8}, // 2
  { 5, 6}, // 3
  { 0, 5}, // 4
  { 5, 5}, // 5
  { 3, 4}, // 6
  { 8, 4}, // 7
  { 1, 3}, // 8
  { 6, 3}, // 9
  { 3, 1}, // 10
  { 7, 1}, // 11
  { 0, 0}, // 12
  { 5, 0}, // 13
};

struct rect {
  int a, b, c, d; // 四角形を構成する4点(data[]のINDEX値，ソートして記録)
  int bits; // 四角形を構成する点をビット位置で記録,3つの四角形の点が重複しないことを高速に確認するため
  int d1, d2, d3, d4; // 辺長(ソートして記録)
  int menseki; // 四角形の面積
} rect[5000]; // 凸四角形の数は3656個
int nrect;

int bit[] = { 0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192};

YesNo used[1+13];

int cmpint(const void *p1, const void *p2) // qsort()の比較関数
{
  return    *(int*)p1 - *(int*)p2;
}

int cmprect( const void *p1, const void *p2) // qsort()の比較関数
{
  const struct rect* v1 = (const struct rect*)p1;
  const struct rect* v2 = (const struct rect*)p2;
  if( v1->d1 != v2->d1) return v1->d1 - v2->d1;
  if( v1->d2 != v2->d2) return v1->d2 - v2->d2;
  if( v1->d3 != v2->d3) return v1->d3 - v2->d3;
  if( v1->d4 != v2->d4) return v1->d4 - v2->d4;
  if( v1->menseki != v2->menseki) return v1->menseki - v2->menseki;
  if( v1->a != v2->a) return v1->a - v2->a;
  if( v1->b != v2->b) return v1->b - v2->b;
  if( v1->c != v2->c) return v1->c - v2->c;
  if( v1->d != v2->d) return v1->d - v2->d;
  return    0;
}

void dupout() // 同一データを除去する
{
  int           n = 0;
  struct rect prev = {0};
  if( nrect < 1) return;
  for( int i=1; i< nrect; i++) {
    if( rect[i].a != rect[n].a ||
        rect[i].b != rect[n].b ||
        rect[i].c != rect[n].c ||
        rect[i].d != rect[n].d ||
        rect[i].d1 != rect[n].d1 ||
        rect[i].d2 != rect[n].d2 ||
        rect[i].d3 != rect[n].d3 ||
        rect[i].d4 != rect[n].d4 ||
        rect[i].menseki != rect[n].menseki) {
      rect[++n] = rect[i];
    }
  }
  nrect = n+1;
}

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);
}

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 calcinfo( int a, int b, int c, int d)
{
  // 辺の長さを計算する。
  int dx1 = data[b].x - data[a].x;
  int dy1 = data[b].y - data[a].y;
  int dx2 = data[c].x - data[b].x;
  int dy2 = data[c].y - data[b].y;
  int dx3 = data[d].x - data[c].x;
  int dy3 = data[d].y - data[c].y;
  int dx4 = data[a].x - data[d].x;
  int dy4 = data[a].y - data[d].y;
  int d1 = dx1*dx1 + dy1*dy1;
  int d2 = dx2*dx2 + dy2*dy2;
  int d3 = dx3*dx3 + dy3*dy3;
  int d4 = dx4*dx4 + dy4*dy4;
  int abcd[4] = { a, b, c, d};
  qsort( abcd, 4, sizeof(int), cmpint);
  int dd[4] = { d1, d2, d3, d4};
  qsort( dd, 4, sizeof(int), cmpint);
  rect[nrect].a = abcd[0];
  rect[nrect].b = abcd[1];
  rect[nrect].c = abcd[2];
  rect[nrect].d = abcd[3];
  rect[nrect].bits = bit[a]+bit[b]+bit[c]+bit[d];
  rect[nrect].d1 = dd[0];
  rect[nrect].d2 = dd[1];
  rect[nrect].d3 = dd[2];
  rect[nrect].d4 = dd[3];
  rect[nrect].menseki = calcmenseki2( data[a].x, data[a].y, data[b].x, data[b].y, data[c].x, data[c].y, data[d].x, data[d].y);
  nrect++;
  return d1+d2+d3+d4;
}

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;
}

YesNo isConvex( int a, int b, int c, int d)
{
  return isConvex( data[a].x, data[a].y, data[b].x, data[b].y, data[c].x, data[c].y, data[d].x, data[d].y);
}

void checkall( int idx, int same)
{
  idx -= same;
  for( int i=0; i< same; i++) {
    for( int j=i+1; j< same; j++) {
      for( int k=j+1; k< same; k++) {
        if( (rect[idx+i].bits & rect[idx+j].bits) ||
            (rect[idx+j].bits & rect[idx+k].bits) || 
            (rect[idx+k].bits & rect[idx+i].bits)) {
        }
        else if( rect[idx+i].menseki == rect[idx+j].menseki &&
                 rect[idx+j].menseki == rect[idx+k].menseki ) {
          ps( "発見\n");
          ps( "[%d]a:%2d,b:%2d,c:%2d,d:%2d, bits:%4x, d1:%2d,d2:%2d,d3:%2d,d4:%2d,%2d\n", idx+i, rect[idx+i].a, rect[idx+i].b, rect[idx+i].c, rect[idx+i].d, rect[idx+i].bits, rect[idx+i].d1, rect[idx+i].d2, rect[idx+i].d3, rect[idx+i].d4, rect[idx+i].menseki);
          ps( "[%d]a:%2d,b:%2d,c:%2d,d:%2d, bits:%4x, d1:%2d,d2:%2d,d3:%2d,d4:%2d,%2d\n", idx+j, rect[idx+j].a, rect[idx+j].b, rect[idx+j].c, rect[idx+j].d, rect[idx+j].bits, rect[idx+j].d1, rect[idx+j].d2, rect[idx+j].d3, rect[idx+j].d4, rect[idx+j].menseki);
          ps( "[%d]a:%2d,b:%2d,c:%2d,d:%2d, bits:%4x, d1:%2d,d2:%2d,d3:%2d,d4:%2d,%2d\n", idx+k, rect[idx+k].a, rect[idx+k].b, rect[idx+k].c, rect[idx+k].d, rect[idx+k].bits, rect[idx+k].d1, rect[idx+k].d2, rect[idx+k].d3, rect[idx+k].d4, rect[idx+k].menseki);
        }
      }
    }
  }
}

int main( int argc, cstring argv[])
{
  int i;
  int cntConvex = 0;
  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( isConvex( a, b, c, d)) {
            calcinfo(a,b,c,d);
            cntConvex++;
          }
          used[d] = NO;
        }
        used[c] = NO;
      }
      used[b] = NO;
    }
    used[a] = NO;
  }
  qsort( rect, nrect, sizeof(rect[0]), cmprect);
  dupout();
  ps( "Convex:%d\n", cntConvex);
#if 0
  for( i=0; i< nrect; i++) {
    ps( "%4d : %2d,%2d,%2d,%2d,辺長(%3d, %3d, %3d, %3d)面積(%4d)\n", i, rect[i].a, rect[i].b, rect[i].c, rect[i].d, rect[i].d1, rect[i].d2, rect[i].d3, rect[i].d4, rect[i].menseki);
  }
#endif
  int same = -1;
  struct rect prev;
  prev.d1 = prev.d2 = prev.d3 = prev.d4 = -1;
  for( i=0; i< nrect; i++) {
    if( rect[i].d1 != prev.d1 ||
        rect[i].d2 != prev.d2 ||
        rect[i].d3 != prev.d3 ||
        rect[i].d4 != prev.d4) {
      if( same >= 3) {          // 同じ四角形が3つなければならない
        checkall( i, same);
      }
      same = 1;
      prev = rect[i];
    }
    else {
      same++;
    }
  }
  return    0;
}