読者です 読者をやめる 読者になる 読者になる

yetnoneの日記

どこぞのPh.D. student。何をやっているかと聞かれると困る。

SRM674 Div2 Medium

TopCoder SRM Div2 Medium

整数の組の点集合が与えられて、任意のxy軸を設定したときに両軸上に乗っている点の数の最大値を求める。 点の数の最大値が50なので全探索で大丈夫。

任意の2点で片方の軸を固定した後、追加でもう1点指定すれば両方の軸が固定されるので、 固定された軸に対して全点がそれぞれ軸上にあるか判定していけばOK。

コードはハンドルネームHalfSummer11さんのものを少し改変(軸に乗っているかどうかの判定の1つ目の式を変更)して引用。

int bestShot(vector <int> x, vector <int> y)
{
    int n = x.size(), ans = 0;
    if (n <= 2) return n;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            for (int k = 0; k < n; ++k){
                if (k != i && k != j){
                    int cnt = 0;
                    int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j], x3 = x[k], y3 = y[k];
                    for (int p = 0; p < n; ++p){
                        int xx = x[p], yy = y[p];
                        if ((1ll * (x2 - x1) * (yy - y1) - 1ll * (y2 - y1) * (xx - x1) == 0) || (1ll * (x3 - xx) * (x2 - x1) + 1ll * (y3 - yy) * (y2 - y1) == 0)) ++ cnt;
                    }
                    ans = max(ans, cnt);
                }
            }
    return ans;
}