エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

2点を対角の頂点とする矩形の内側の点を判別せよ

オフラインリアルタイムどう書く第6回の参考問題 - Qiita」は前回一度解いていますが、別の方法――対象となる点をすべて数え上げるという方法で解く場合のお話。この問題では判定が必要な点の個数は10×10のたかだか100とわかっているので、こういう力技法でもOK。


で。問題を解くためには。(0, 0)から(9, 9)までの点のうち、どの点が重なった領域の内部の点であるかを判断しなければならないわけですが。そのためにはまず、点が範囲内か否かを判断する必要があります。

任意の数xが、2数x1、x2のあいだにあるか否かを判定せよ

まずは一次元から。
とその前に。定義から。「あいだにある」というのは境界上のばあいも含む、つまりx=x1やx=x2のばあいも含むとします。なのでx=x1=x2もアリとします。
ここでたとえばx1≦x2ということであれば、x1≦x∧x≦x2で判定できますが、いまはx1とx2の大小は決まっていません。なのでここではx1とx、x2とxとの関係に着目します。
x1、x2おのおのからxを引いた(x1 - x)、(x2 - x)は、xがx1とx2のあいだにあるばあい、一方が0か正の値でもう一方が0か負の値になります。これがあいだにないばあいは、どちらも正の値かどちらも負の値かになります。結果としてその積(x1 - x)(x2 - x)はxがx1とx2のあいだにあるばあいにだけ0以下の値になります。


これをふまえて。述語betweenを定義すると。

C++だと、こんな感じ。

bool between(int x1, int x2, int x)
{
    return ((x1 - x) * (x2 - x)) <= 0;
}


Haskellだと、こんな感じ。

between x1 x2 x = (x1 - x) * (x2 - x) <= 0

任意の点(x, y)が、2点(x1, y1)、(x2, y2)を対角の頂点とする矩形の内部にあるか否かを判定せよ

単に「2点を対角の頂点とする矩形」と言ってしまうと際限がないのでキチンと定義しないといけないのですが。このばあい辺がx軸y軸に平行な矩形ですね。(x1, y1), (x2, y1), (x1, y2), (x2, y2)の4点を頂点とする矩形、と言ってもいいかもしれません。今回も辺の上も内部として、矩形でなく線分になってしまうばあい(つまりx1 = x2のばあいやy1 = y2のばあい)や点になってしまうばあい(x1 = x2かつy1 = y2のばあい)もアリとします。そのばあいは線分上や点上にあるばあいを内部にあるとします。


一次元ではすでにできているので、あとはx軸y軸それぞれについて判定すればよいわけで。述語insideを定義すると。

C++だと、こんな感じ。

bool inside(int x1, int y1, int x2, int y2, int x, int y)
{
    return between(x1, x2, x) && between(y1, y2, y);
}


Haskellだと、こんな感じ。

inside x1 y1 x2 y2 x y = (between x1 x2 x) && (between y1 y2 y)


さてここで。
述語insideを簡単に定義できたのはよいのですが、ここでbetweenを展開して考えてみると。(x1 - x)(x2 - x)と(y1 - y)(y2 - y)がともに0以下のばあい述語insideが真になります。(x1 - x)と(x2 - x)の積が0以下になるか否かで判定ができたように、算術演算を使ってできないだろうか、と考えてしまうわけです。

結論から言うと。そのような式を見つけられませんでした orz 。2つの値がともに負の値か否かという判定であれば、最上位ビットの論理積をとるといった乱暴な手段も考えられたのですが、0が入ってくるととたんにむずかしくなり、お手上げとなりました。


もう一息という感じが、すごく悔しさを助長します。

そんなわけで。実装


全実装はGitHubに置いてあります。

ここでは解の部分のコードだけ転載します。

C++


演算の本体より文字列操作のためのコードが多くなってしまうのがC++の難点。

#include "answer.hpp"

#include <sstream>

bool between(int x1, int x2, int x)
{
    return ((x1 - x) * (x2 - x)) <= 0;
}

bool inside(int x1, int y1, int x2, int y2, int x, int y)
{
    return between(x1, x2, x) && between(y1, y2, y);
}

std::string solve(const std::string& s)
{
    std::istringstream iss(s);

    int  p1, p2, p3, p4, p5, p6;
    char h1, h2, c1, h3, h4;

    iss >> p1 >> h1 >> p2 >> h2 >> p3 >> c1 >> p4 >> h3 >> p5 >> h4 >> p6;

    if((h1 != '-') || (h2 != '-') || (h3 != '-') || (h4 != '-') || (c1 != ',') || ( ! iss.eof()))
    {
        return "-";
    }

    int x11 = p1 / 10, y11 = p1 % 10;
    int x12 = p2 / 10, y12 = p2 % 10;
    int x13 = p3 / 10, y13 = p3 % 10;
    int x21 = p4 / 10, y21 = p4 % 10;
    int x22 = p5 / 10, y22 = p5 % 10;
    int x23 = p6 / 10, y23 = p6 % 10;

    int count = 0;
    for(int y = 0; y < 10; ++y)
    {
        for(int x = 0; x < 10; ++x)
        {
            if( (inside(x11, y11, x12, y12, x, y) || inside(x11, y11, x13, y13, x, y)) && (inside(x21, y21, x22, y22, x, y) || inside(x21, y21, x23, y23, x, y))  )
            {
                ++count;
            }
        }
    }

    std::ostringstream oss;

    oss << count;

    return oss.str();
}
Haskell


リストの長さを数えています。リストの中身は何でもよいので「1」にしてますが、なんか不格好。「条件に合うばあいの個数」を得るような関数とかが欲しいところ。

module Answer(solve) where
 
type Pos = (Int, Int)
 
between x1 x2 x = (x1 - x) * (x2 - x) <= 0
 
inside x1 y1 x2 y2 x y = (between x1 x2 x) && (between y1 y2 y)
 
l_intersect :: (Pos, Pos, Pos) -> (Pos, Pos, Pos) -> String
l_intersect ((x11, y11), (x12, y12), (x13, y13)) ((x21, y21), (x22, y22), (x23, y23)) =
    show $ length [1| x <- [0..9], y<-[0..9], ((inside x11 y11 x12 y12 x y) || (inside x11 y11 x13 y13 x y)) && ((inside x21 y21 x22 y22 x y) || (inside x21 y21 x23 y23 x y))]
 
solve :: String -> String
solve [x11,y11,'-',x12,y12,'-',x13,y13,',',x21,y21,'-',x22,y22,'-',x23,y23] =
    l_intersect ((read [x11], read [y11]), (read [x12], read [y12]), (read [x13], read [y13]))
                ((read [x21], read [y21]), (read [x22], read [y22]), (read [x23], read [y23]))