正方形を見つける問題をJavaで解いてみた。

　正方形を見つける問題をJavaで解いてみました。(^_^;
　昨日、自分で求めた正方形の個数を求める問題をJavaでプログラムを作って、4点の組合せを生成して条件に合うものをカウントする方法で求めました。

●NumOfSquare1.java

/* 
 * NumOfSquare1.java
 * 
 * +---+---+---+---+   0     1     2     3     4
 * |   | +-+-+ |   |            5  6  7         
 * +---+-+-+-+-+---+   8     9 10 11 12 13    14
 * |   | +-+-+ |   |           15 16 17         
 * +---+---+---+---+  18    19    20    21    22
 * |   | +-+-+ |   |           23 24 25         
 * +---+-+-+-+-+---+  26    27 28 29 30 31    32
 * |   | +-+-+ |   |           33 34 35         
 * +---+---+---+---+  36    37    38    39    40
 * 
 */

class NumOfSquare1 {
    // 順列生成
    static boolean nextPerm(int[] p, int n, int r) {
        int i, j;
        int t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j = n - 1; i < j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    // 組合せ生成
    static boolean nextComb(int[] p, int n, int r) {
        for_cont: for(;;){
            if(!nextPerm(p,n,r)) return(false);
            for(int i=0; i< r-1; i++)
                if(p[i]> p[i+1]) continue for_cont;
            break;
        }
        return(true);
    }
    
    public static void main(String[] args) {
        final int N = 41;
        int count=0;
        int[] p = new int[N];
        int[] j = {0,1,2,3,4,8,9,11,13,14,18,19,20,21,22,26,27,29,31,32,36,37,38,39,40};
        Point[] point = new Point[N];
        for(int i=0; i< N; i++) p[i]=i;
        
        for(int i=0; i< 25; i++)
            point[j[i]] = new Point((i%5)*2,(i/5)*2);
        
        point[ 5] = new Point(3,1); point[ 6] = new Point(4,1); point[ 7] = new Point(5,1);
        point[10] = new Point(3,2);                           ; point[12] = new Point(5,2);
        point[15] = new Point(3,3); point[16] = new Point(4,3); point[17] = new Point(5,3);
        
        point[23] = new Point(3,5); point[24] = new Point(4,5); point[25] = new Point(5,5);
        point[28] = new Point(3,6);                           ; point[30] = new Point(5,6);
        point[33] = new Point(3,7); point[34] = new Point(4,7); point[35] = new Point(5,7);
        
        long tm=System.nanoTime();      // Timer Start
        
        do{
            if(15<=p[0] && p[0]<=17) continue;
            if(33<=p[0] && p[0]<=35) continue;
            if(36<=p[0] && p[0]<=40) continue;
            if(point[p[0]].x!=point[p[2]].x) continue;
            if(point[p[1]].x!=point[p[3]].x) continue;
            if(point[p[0]].y!=point[p[1]].y) continue;
            if(point[p[2]].y!=point[p[3]].y) continue;
            if(point[p[0]].squDistance(point[p[1]])!=point[p[0]].squDistance(point[p[2]]))
                continue;
            // チェックを潜り抜けたものだけをカウント
            count++;
        }while(nextComb(p,N,4));
        System.out.println("count="+count);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}

class Point {
    int x = 0, y = 0;
    // コンストラクタ
    Point(){ }
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
    // 距離の2乗を求める
    int squDistance(Point p){
        int dx = x - p.x;
        int dy = y - p.y;
        return (dx * dx + dy * dy);
    }
}