http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1765

枚举k,然后用 vis 数组标记的方式 O(n) 计算出答案。

(只贴出与题目有关的代码,宏定义见 GitHub

/* 0.472s */
const int mx = int(2e3) + 5;
const double eps = 1e-8;
struct comp {bool operator()(const double a, const double b)const {return a + eps < b;}};
#define Lpos(a, n, x) (lower_bound(a, a + (n), x, comp()) - (a))

double alpha[mx];
int n;
bool vis[mx];

int solve(int k)
{
    mem(vis, 0);
    int i, j, ans = 0, pos;
    double alp, d = 2 * pi / k;
    for (i = 0; i + k <= n; ++i)
    {
        if (vis[i]) continue;
        alp = alpha[i];
        Forr(j, 1, k)
        {
            alp += d; // 不推荐用 +=d 的方式,还好误差不是很大
            pos = Lpos(alpha, n, alp);
            if (pos == n || fabs(alp - alpha[pos]) > eps) break; // 未找到
            vis[pos] = true;
        }
        if (j == k) ++ans;
    }
    return ans;
}

int main()
{
    int i, k, ans;
    double x, y;
    while (SI(n), n)
    {
        Pcas();
        For(i, n) SDD(x, y), alpha[i] = atan2(y, x);
        sort(alpha, alpha + n);
        Forr(k, 3, n + 1) if (ans = solve(k)) PII(k, ans);
    }
    return 0;
}

Comments

comments powered by Disqus