0. 自己紹介

初めまして！　AtCoderを楽しむ高校生です。
Qiitaは実質初投稿ですので至らない点があるかと思いますがよろしくお願いします。

1. ボードゲーム「共円」とは

正方形のマス目があり¹、その格子点に何人かで1つずつ点を置いていくのですが、「置かれてある点の中から異なる4点をどのように取っても、それらが同一円周上（共円）でない、かつ同一直線上（共線）でない」ようにします（説明が下手）。

たとえば、共円（kyouen）で遊べます。

共円には定石（型みたいなもの）もあり、以下のサイトが詳しいです。
ボードゲーム『共円』について - 灘校数研の旧HP

～注意～

以下では、直線を半径無限大の円と考え、共線のことも含めて「共円」と呼ぶことにします。
また、以下で掲示する画像はいずれも共円（kyouen）から取得したものです。

2. 何をやるか

「これ以上どこに置いても共円が出来てしまう」という状態は必ず訪れます。この状態を飽和と呼び、これまでに置いた点の数を 決まり手数 と呼ぶことにしましょう。

ここでは、$n\times n$ の格子点の集まりに対する 決まり手数の範囲らしきもの を求めるプログラムを作りたいです。また、そのときの点の置き方も出力したいと思います。

以下は、$7\times 7$ の飽和した状態で、このときの決まり手数は $10$ です。

3. プログラミングの手順

3.1. 環境・言語

wandboxを使います。言語はC++です。
競プロっぽいコードの書き方をしていると思いますが、どうかご了承ください。
まずは下に使用するテンプレをあげておきます。

template.cpp

#pragma GCC optimize("Ofast") // これは単なる高速化
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,k,n) for(int i=k;i<int(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define fi first
#define se second
using P=pair<int,int>;
using vi=vector<int>;
using vvi=vector<vi>;
constexpr int INF=1001001001;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}

3.2. 共円判定

異なる4点が共円であることはどのように判定すればよいだろう？っと思って調べてみると、4点が同一円周上にある条件 - 受験の月がヒットしました。

どうやら格子点を複素数平面と見て、$\frac{(\beta-\gamma)(\alpha-\delta)}{(\alpha-\gamma)(\beta-\delta)}\in\mathbb{R}$は、4点 A($\alpha$), B($\beta$), C($\gamma$), D($\delta$)が共円または共線であることと同値であるようです。

これを実装すると、以下のようになりました²。

kyouenjudge.cpp

// 複素数の差
P diff(P a,P b){
    return P(a.fi-b.fi,a.se-b.se);
}
// 複素数の積
P prod(P a,P b){
    int a1=a.fi,a2=a.se;
    int b1=b.fi,b2=b.se;
    return P(a1*b1-a2*b2,a1*b2+a2*b1);
}
// 4点の共円判定
bool kyouen(P a,P b,P c,P d){
    P x=prod(diff(a,c),diff(b,d));
    P y=prod(diff(b,c),diff(a,d));
    return x.fi*y.se==x.se*y.fi;
}

3.3. 結局どう調べるか

こんな流れでいきます:
　　ランダムな点Pを指定（すでに調べてたら無視）
　-> すでに置かれてる点3つとPの組み合わせで共円が生じるかチェック
　-> 生じないならPを置く
　-> 飽和したら、決まり手数を記録（更新）して初期化
これを、指定した時間制限いっぱい繰り返します。

main.cpp

int main(){
    srand((unsigned)time(NULL)); // randomのおまじない
    // ただの高速化
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n; cin>>n; // マス目大きさ
    double limit; cin>>limit; // 時間制限(10秒まで)

    vector<P> v;
    vvi used(n,vi(n,0));
    int ansM=0,ansm=INF; // ansM:=最大決まり手数, ansm:=最小決まり手数
    INT cnt=0,ope=0; //cnt:=置いた点の数, ope:=試行回数
    vector<P> tM,tm; //tM:=手数ansMのときの点, tm:=手数ansmのときの点

    //時間いっぱいrandomに探索
    while(double(clock())/double(CLOCKS_PER_SEC)<limit){
        // randomに点を指定
        int a=rand()%n,b=rand()%n;
        P p=P(a,b);
        // すでに調べてたら操作しない
        if(used[p.fi][p.se]) continue;
        used[p.fi][p.se]=1;
        if(v.size()<3){
            cnt++;
            v.eb(p);
        }
        else{
            int sz=v.size();
            // 共円になり得るか判定
            bool f=true;
            rep(i,sz-2){
                if(!f) break;
                REP(j,i+1,sz-1){
                    if(!f) break;
                    REP(k,j+1,sz){
                        if(kyouen(v[i],v[j],v[k],p)){
                            f=false; break;
                        }
                    }
                }
            }
            if(f){
                cnt++;
                v.eb(p);
            }
        }

        // 飽和したら初期化
        bool g=true;
        rep(i,n)rep(j,n) g=g&&used[i][j];
        if(g){
            rep(i,n)rep(j,n) used[i][j]=0;
            if(chmax(ansM,cnt)) tM=v;
            if(chmin(ansm,cnt)) tm=v;
            v.clear();
            cnt=0;
            ope++;
        }
    }

    sort(all(tM));
    sort(all(tm));

    // 結果出力
    cout<<"-Trials: "<<ope<<'\n';
    out("-Points");
    cout<<"   MAX "<<ansM<<": ";
    outvp(tM);
    cout<<"   min "<<ansm<<": ";
    outvp(tm);
}

3.4. 出力された点を打ってみた

$n=8$ で $5$ 秒試行すると...

これを共円（kyouen）に打ち込んでみます。

最大とおもわしき決まり手数(15)

最小とおもわしき決まり手数(9)

スカスカですね（笑）

どうやら例の共円判定は正しそうですね。

3.5. 計算量と問題点

1回点を置く操作（whileループの中身）での計算量を考えます。

置かれている点の個数を $m$ とおくと、共円判定は最大 $_m\mathrm{C}_3$ 回です。また、飽和しているかどうか判定するのに $n^2$ 回計算します。
よって、 $\mathcal{O}(n^2+m^3)$ くらいでしょうか³。
これだと $n=80$ でも1回の試行に10秒以上かかります。だめですね...

それに、random（つまり何も考えずに）に置く点を決めているので、数万回試行できても、その決まり手数が最大・最小であることは保証できないこともあります。

4. 最後に

実行できるコードをはっておきます-> こちら
ぜひ遊んでみてください。

また、共円に関する面白い記事を貼っておきます -> ボードゲーム「共円」に学ぶ、ガウス整数 x + yi の世界 - drken

最後まで読んでいただき誠にありがとうございました。

（余談） 遊びに行けないゴールデンウィーク、ストレス溜まりましたわ。

5. 追記

飽和したか判定するのは、わざわざusedの中身が全部0になったか調べなくても、usedにした点の数を数えていけばよいだけですよね。
しかし、これでもあまり改善されませんでした。

でも、改良の余地だらけな気がする...

正方形を用いないこともあるそうです。 ↩
複素数の実部と虚部をpairで格納しております。 ↩
ちゃうかもよ ↩

共円ゲームの決まり手数を考えてみた