luogu 1369
2024-08-27 00:52:37
给出平面上的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 ;
}
最新文章
- AngularJs2与AMD加载器(dojo requirejs)集成
- PHP AES的加密解密
- 关于近段时间论坛型APP 的一段舍弃
- Yii2中的零碎知识点
- 软件工程day7
- ASP.NET MVC Bootstrap极速开发框架
- double int char 数据类型
- MFC菜单、工具栏和状态栏
- 探讨VMP 2.12.3 导入表修复
- 有关Repeater的事件
- D其他项目打电话AL工程EF Model
- HTML5画布(CANVAS)速查简表
- javascript语法之声明变量
- 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
- svn介绍
- 使用Cobbler批量部署Linux和Windows:CentOS/Ubuntu批量安装(二)
- 【Ray Tracing The Next Week 超详解】 光线追踪2-4 Perlin noise
- Hadoop 系列(一)基本概念
- mysql 加入远程用户
- Java 获取指定包下的所有类