SRM599(div1) Med: FindPolygons

昨日こんなことをし始めました。

hyoga.hatenablog.com

ただ、今の自分は黄色手前の青。div1Easyは流石に解けていないといけない領域です。ということで、一緒にMedも解くことで精進をしよう！というのが本来の趣旨です（絶対分かるかこんなん）

問題

2次元平面に多角形を作りましょう。ただ、以下のルールがあります。

• 全ての点は格子点上に存在する
• 周の長さが丁度L(integer)

この制約下で、「最も辺の数が少ない」多角形を見つけてください。存在しないなら-1、存在するなら、その中で最も「最長の辺の長さ-最短の辺の長さ」が小さいものを見つけ、その評価値（＝最長-最短）を返してください。

1≦L≦5,000です。

解説

普通に難しい。取り敢えず四角形は絶対作れるので、Lが4以上の偶数の時はOKです。逆にL=1,2,3は全部-1。

取り敢えず三角形を作ることを考えましょう。1点は原点でOKで、もう2点をループ回すと当然死にます…流石に三角不等式から探索範囲は2,500×2,500に絞られるとしても無理です。
ところで、辺の長さが整数で無い場合死にます。というのも、根号を加算で消滅させることは出来ないので。

ということで、L/2×L/2の中で辺の長さ毎にvectorに突っ込んでいきます。判定は適当にd=getDist→dd=xx+y*yとしました。
その後、1辺目の長さ→頂点1つ目→2辺目の長さ→頂点2つ目でループを回します。こうすると、検出される点は全て原点からの距離計算の時、x軸上y軸上に無い時は「直角三角形の斜辺」に相当します。多分これは1組しかないので、各長さの点の個数は高々4個（多分）。ということで、計算量がO(L²)に収まります。
その中で最後の辺の長さが丁度良ければその評価値の最小値を求めて終わり。この際、サンプルに引っかかるので3点が1直線に並ぶ場合を外します。

ところで、周の長さが奇数になる三角形は存在しなさそうです（実験）。五角形以降は考えてない（白目）けど、それなりに実験重ねて「奇数長で作るのは無理！」って投げたら通りました。kmjpプロの解説がとても分かりやすいのでこっち参照（この解説の意味とは）

kmjp.hatenablog.jp

inline double getDist(double x, double y)
{
    return sqrt(x * x + y * y);
}

struct FindPolygons
{
    inline bool sameVector(pii a, pii b)
    {
        if (a.first == 0)
            return b.first == 0;
        return a.second * b.first == b.second * a.first;
    }
    double L;
    double minimumPolygon(int _L)
    {
        L = _L;
        if (_L & 1 || _L == 2)
            return -1;
        // can you make triangle?
        map<int, vector<pair<double, double>>> mp;
        for (int i = 0; 2 * i - L < eps; i++)
        {
            for (int j = 0; getDist(i, j) - L < eps; j++)
            {
                int d = getDist(i, j);
                if (d * d == i * i + j * j)
                {
                    mp[d].push_back(mp(i, j));
                }
            }
        }
        int ret = 1e9;
        for (int a = 1; 2 * a - L < eps; a++)
        {
            auto fst = mp[a];
            rep(i, fst.size())
            {
                for (int b = 1; b < min(a, (_L - a)); b++)
                {
                    auto scn = mp[b];
                    rep(j, scn.size())
                    {
                        if (sameVector(fst[i], scn[j]))
                            continue;
                        int x = fst[i].first - scn[j].first;
                        int y = fst[i].second - scn[j].second;
                        int d = getDist(x, y);
                        if (d * d == x * x + y * y && a + b + d == _L)
                        {
                            ret = min(ret, max(a, max(b, d)) - min(a, min(b, d)));
                        }
                    }
                }
            }
        }
        if (ret != 1e9)
        {
            return ret;
        }
        int halfL = L / 2;
        ret = ((int)(halfL + 1) / 2) - ((int)halfL / 2);
        return ret;
    }
};

感想

普通にやっていて記事を毎回更新するとこれ死ぬな？（以降まとめたりすることを考えます）