给出平面上的n个点,请找出一个边与坐标轴平行的矩形,使得它的边界上有尽量多的点

模拟退火题解
$n^2$ 处理每行的前缀和与每列的前缀和
退火50次即可

#include <bits/stdc++.h>

const int N = ;

int n, A[N][N];
int sum_h[N][N], sum_l[N][N];
int Max_n = , Max_m = ; #define gc getchar() inline int read() {
int x = ;
char c = gc;
while(c < '' || c > '') c = gc;
while(c >= '' && c <= '') x = x * + c - '', c = gc;
return x;
} #define DB double const DB Max_tmp = , Del = 0.98; int Get_ans(int l, int r, int u, int d) {
if(l == r && u != d) {
return sum_l[d][l] - sum_l[u - ][l];
} else if(l != r && u == d) {
return sum_h[u][r] - sum_h[u][l - ];
} else if(l == r && u == d) {
return A[l][u];
} else {
int ret = ;
ret += (sum_h[u][r] - sum_h[u][l - ])
+ (sum_h[d][r] - sum_h[d][l - ])
+ (sum_l[d][l] - sum_l[u - ][l])
+ (sum_l[d][r] - sum_l[u - ][r]);
if(A[u][l]) ret --;
if(A[u][r]) ret --;
if(A[d][l]) ret --;
if(A[d][r]) ret --;
return ret;
}
} inline int MNTH() {
DB Now_tmp = Max_tmp;
int l = rand() % Max_m + , r = rand() % Max_m + , u = rand() % Max_n + , d = rand() % Max_n + ;
int Now_ans = Get_ans(l, r, u, d);
while(Now_tmp > 0.01) {
int l_ = l, r_ = r, u_ = u, d_ = d;
int opt = rand() % + ;
if(opt == ) l_ = rand() % Max_m + ;
else if(opt == ) r_ = rand() % Max_m + ;
else if(opt == ) u_ = rand() % Max_n + ;
else d_ = rand() % Max_n + ;
int Ls_ans = Get_ans(l_, r_, u_, d_);
if(Ls_ans > Now_ans || (Ls_ans < Now_ans && exp((Ls_ans - Now_ans) / Now_tmp) * RAND_MAX) >= rand())
Now_ans = Ls_ans, l = l_, r = r_, u = u_, d = d_;
Now_tmp *= Del;
}
return Now_ans;
} int main() {
srand(time() + );
n = read();
for(int i = ; i <= n; i ++) {
int x = read(), y = read();
A[x][y] = ;
Max_n = std:: max(Max_n, x), Max_m = std:: max(Max_m, y);
}
for(int i = ; i <= Max_n; i ++)
for(int j = ; j <= Max_m; j ++)
sum_h[i][j] = sum_h[i][j - ] + A[i][j];
for(int i = ; i <= Max_m; i ++)
for(int j = ; j <= Max_n; j ++)
sum_l[j][i] = sum_l[j - ][i] + A[j][i];
int T = ;
int Answer = -;
for(; T; T --) Answer = std:: max(Answer, MNTH());
printf("%d", Answer);
return ;
}

最新文章

  1. AngularJs2与AMD加载器(dojo requirejs)集成
  2. PHP AES的加密解密
  3. 关于近段时间论坛型APP 的一段舍弃
  4. Yii2中的零碎知识点
  5. 软件工程day7
  6. ASP.NET MVC Bootstrap极速开发框架
  7. double int char 数据类型
  8. MFC菜单、工具栏和状态栏
  9. 探讨VMP 2.12.3 导入表修复
  10. 有关Repeater的事件
  11. D其他项目打电话AL工程EF Model
  12. HTML5画布(CANVAS)速查简表
  13. javascript语法之声明变量
  14. 18/03/18 04:53:44 WARN TaskSchedulerImpl: Initial job has not accepted any resources; check your cluster UI to ensure that workers are registered and have sufficient resources
  15. svn介绍
  16. 使用Cobbler批量部署Linux和Windows:CentOS/Ubuntu批量安装(二)
  17. 【Ray Tracing The Next Week 超详解】 光线追踪2-4 Perlin noise
  18. Hadoop 系列(一)基本概念
  19. mysql 加入远程用户
  20. Java 获取指定包下的所有类

热门文章

  1. (未完成)ARM-linux 移植 SDL
  2. php反转输出字符串(两种方法)
  3. vmware vSphere Data Protection 6.1 --------1-部署
  4. .net SHA-256 SHA-1
  5. 预编译And作用域链
  6. HibernateTemplate的queryForList(sql)用法
  7. 宽字节 多字节 mbstowcs wcstombs
  8. java基础点
  9. 改变说明文档显示位置wrap
  10. 【nodejs代理服务器三】nodejs注册windows服务