luogu 1369

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

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

#include <bits/stdc++.h>

const int N = 102;

int n, A[N][N];
int sum_h[N][N], sum_l[N][N];
int Max_n = 0, Max_m = 0;

#define gc getchar()

inline int read() {
    int x = 0;
    char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}

#define DB double

const DB Max_tmp = 1000, 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 - 1][l];
    } else if(l != r && u == d) {
        return sum_h[u][r] - sum_h[u][l - 1];
    } else if(l == r && u == d) {
        return A[l][u];
    } else {
        int ret = 0;
        ret += (sum_h[u][r] - sum_h[u][l - 1])
               +  (sum_h[d][r] - sum_h[d][l - 1])
               +  (sum_l[d][l] - sum_l[u - 1][l])
               +  (sum_l[d][r] - sum_l[u - 1][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 + 1, r = rand() % Max_m + 1, u = rand() % Max_n + 1, d = rand() % Max_n + 1;
    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() % 4 + 1;
        if(opt == 1) l_ = rand() % Max_m + 1;
        else if(opt == 2) r_ = rand() % Max_m + 1;
        else if(opt == 3) u_ = rand() % Max_n + 1;
        else d_ = rand() % Max_n + 1;
        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(0) + 19991206);
    n = read();
    for(int i = 1; i <= n; i ++) {
        int x = read(), y = read();
        A[x][y] = 1;
        Max_n = std:: max(Max_n, x), Max_m = std:: max(Max_m, y);
    }
    for(int i = 1; i <= Max_n; i ++)
        for(int j = 1; j <= Max_m; j ++)
            sum_h[i][j] = sum_h[i][j - 1] + A[i][j];
    for(int i = 1; i <= Max_m; i ++)
        for(int j = 1; j <= Max_n; j ++)
            sum_l[j][i] = sum_l[j - 1][i] + A[j][i];
    int T = 50;
    int Answer = -1;
    for(; T; T --) Answer = std:: max(Answer, MNTH());
    printf("%d", Answer);
    return 0;
}