Codeforces 460E Roland and Rose(暴力)

题目链接：Codeforces 460E Roland and Rose

题目大意：在以原点为圆心，半径为R的局域内选择N个整数点，使得N个点中两两距离的平方和最大。

解题思路：R最大为30，那么其实距离圆心距离最大的整数点不过12个最多，直接暴力枚举。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

struct point {
    int x, y;
    point (int x = 0, int y = 0) {
        this->x = x;
        this->y = y;
    }
};

int N, R, M, ans, pos[10], rec[10];
vector<point> vec;

inline int dis (int x, int y) {
    return x * x + y * y;
}

inline bool cmp (const point& a, const point& b) {
    return dis(a.x, a.y) > dis(b.x, b.y);
}

void init () {
    scanf("%d%d", &N, &R);
    for (int i = -R; i <= R; i++) {
        for (int j = -R; j <= R; j++)  {
            if (i * i + j * j <= R * R)
                vec.push_back(point(i, j));
        }
    }

    ans = 0;
    M = min((int)vec.size(), 18);
    sort(vec.begin(), vec.end(), cmp);
}

void dfs (int d, int f, int s) {
    if (d == N) {
        if (s > ans) {
            ans = s;
            memcpy(rec, pos, sizeof(pos));
        }
        return;
    }

    for (int i = f; i < M; i++) {
        int add = 0;
        for (int j = 0; j < d; j++)
            add += dis(vec[pos[j]].x - vec[i].x, vec[pos[j]].y - vec[i].y);
        pos[d] = i;
        dfs(d + 1, i, s + add);
    }
}

int main () {
    init();
    dfs(0, 0, 0);
    printf("%d\n", ans);
    for (int i = 0; i < N; i++)
        printf("%d %d\n", vec[rec[i]].x, vec[rec[i]].y);
    return 0;
}