不定期解説記事企画 ARC018 B #雫ぷよ

　こんにちは、研究室のミーティングで論文紹介をしたら人にものを伝える技術が絶望的にないことが分かった綿谷雫です。 解説記事を書いたら人に伝わる文章が書けるようになるかもしれないので、今日は解説記事を書いてみたいと思います。

　今回扱う問題はAtCoder Regular Contest 018 B - 格子点と整数です。リンクを下に貼っておきます。

atcoder.jp

AtCoder Problems*1のUserPageのRecommendationのModerateにあったものから適当に選びました。

問題概要

• 格子点がいくつか与えられる。
• 与えられた格子点を結んでできる三角形のうち面積が整数のものの数を求める。
• ただし面積0の三角形は三角形として認めない。

という問題でした。〜が好きだ、という特徴的な問題文は漫画『HELLSING』に出てくる演説が元ネタでしょう。

考察

まず与えられる格子点の数を見てみるととあるので、格子点3つの組は組よりも少ないです。 なので、1組ずつ面積が整数か、面積が0になっていないか、を調べきちんと面積が整数だったものを数えていっても間に合いそうです。

解法

さて、実際に1組ずつ面積が整数か、面積が0になっていないかを 整数になるかどうかチェックするためには、面積の求め方をそもそも知っておく必要があります。

3つの点が与えられたら三角形の面積は決まりそうなので、人類の叡智を信じて「三点　三角形　面積」で検索します。 すると三角形の面積は三点の座標を用いて次のように表されることがわかります。

この式から

• 面積が整数であるためにはの部分が2で割り切れる必要があること
• 面積Sが0でないためにはの部分が0でないこと が必要だとわかります。

そこでの部分をとおき、S2が2で割り切れて0でないかを確認するlogical関数を 作ります。

logical function check(i,j,k)
    integer,intent(in)::i,j,k
    check=.true.
    if(mod(S2(i,j,k),2)/=0)check=.false.
    if(S2(i,j,k)==0_16)check=.false.
end function
integer(16) function S2(i,j,k)
    integer,intent(in)::i,j,k
    S2=(X(i)-X(k))*(Y(j)-Y(k))-(X(j)-X(k))*(Y(i)-Y(k))
end function

あとは、これを使ってコードを書いていけば完成です。 格子点の座標の制約がとのことなのでがオーバーフローしないように注意します。

出来上がったコード全体がこちらです。

program am
implicit none
integer::N
integer(16),allocatable,dimension(:)::X,Y
integer::ans

integer::i,j,k
read*,N
allocate(X(N),Y(N))
do i=1,N
    read*,X(i),Y(i)
end do
ans=0
do i=1,N-2
    do j=i+1,N-1
        do k=j+1,N
            if(check(i,j,k))ans=ans+1
        end do
    end do
end do

print"(I0)",ans

contains
logical function check(i,j,k)
    integer,intent(in)::i,j,k
    check=.true.
    if(mod(S2(i,j,k),2)/=0)check=.false.
    if(S2(i,j,k)==0_16)check=.false.
end function
integer(16) function S2(i,j,k)
    integer,intent(in)::i,j,k
    S2=(X(i)-X(k))*(Y(j)-Y(k))-(X(j)-X(k))*(Y(i)-Y(k))
end function

end program am

おしまい。

*1:https://kenkoooo.com/atcoder/#/table/