Codeforces 460E Roland and Rose(暴力)
2024-09-04 07:12:19
题目链接: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;
}
最新文章
- 用户信息 Froms验证票证
- 【转帖】四种BI 开源工具介绍-SpagoBI,openI,JasperSoft,Pentaho
- Swift开发学习-02 变量和常量
- suse linux 操作系统下打BASH补丁
- BIOS+MBR模式 VS UEFI+GPT模式
- opengl模板缓冲区
- 【NET】Winform分页控件初探
- [原创]一款小巧、灵活的Java多线程爬虫框架(AiPa)
- arcgis更改栅格数据范围
- BeautifulSoup库
- shell-整理目录下的备份文件并生成压缩包
- 排名前10的vue前端UI框架框架值得你掌握
- 为什么要用nginx
- linux 使用错误总结
- requestAnimationFrame优势何在?
- 字符测试篇isalnum isalpha isascii iscntrl isdigit isgraphis islower isprint isspace ispunct isupper isxdigit
- linux加程序是否当掉检测脚本
- 数字图像处理实验(9):PROJECT 04-05,Correlation in the Frequency Domain 标签: 图像处理MATLAB 2017-05-25 10:14
- JVM内存溢出及配置
- 获得NOTEPAD++ Download Manager的所有下载列表的内容的au3脚本
热门文章
- Exercise01_02
- Services
- 专访阿里巴巴研究员“赵海平”:Facebook的PHP底层性能优化之路(HipHop,HHVM)
- 定期访问WebLogic Server返回状态的脚本
- &#39;dict_values&#39; object does not support indexing, Python字典dict中由value查key
- Python图像处理(16):图像金字塔
- OpenGL.Vertex Array Object (VAO) [转]
- 【云计算】mesos+marathon 服务发现、负载均衡、监控告警方案
- 从HTML5移动应用现状谈发展趋势
- Java 关于容器集合等数据结构详情图解,一目了然