题意

求包含 A 类点但是不包含 B 类点的矩形，要求 A 类点尽可能多，在此基础上面积最小。点个数不大于 $500$ ，坐标介于 $[0,1000]$ 之间。

思路

正解悬线法看不懂思密达，目测正解复杂度 $O(n^3)$ ，那就考虑乱搞，把 B 都加入二维树状数组，然后假贪心，也就是每次模拟按照某种打乱后的顺序无脑加点，如果当前点加入会导致包含 B ，就放弃，反之就无脑加。

然后迭代轮数通过时间给限制。所以本地调试的时候要用 freopen 而不是手动输入来测试时间。随机个 500ms 这题差不多就能过。还过不了就往上调，这一点类似于模拟退火调整精度。

这题还有一个坑点是坐标可以为 $0$ ，所以所有点坐标要加上 1 否则朴素 2D BIT 会因为 lowbit 死循环。

但愿没有乱搞做法学傻了然后再场上被乱搞做法打乱思路。

代码

#include <stdio.h>
#include <time.h>
#include <algorithm>
#include <chrono>
#include <random>
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const double THRESHOLD = 0.5;
int rd()
{
    int k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9')
        f = (s == '-') ? 0 : f, s = getchar();
    while (s >= '0' && s <= '9')
        k = (k << 1) + (k << 3) + (s ^ '0'), s = getchar();
    return f ? k : -k;
}
char rd_op()
{
    char c = getchar();
    while (c < 'A' || c > 'Z')
        c = getchar();
    return c;
}
void wr(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int N = 505, V = 1001;
namespace bit_2d
{
    int bit[V + 10][V + 10];
    inline int lowbit(int x) { return x & (-x); }
    inline void modify(int x, int y)
    {
        for (int i = x; i <= V; i += lowbit(i))
            for (int j = y; j <= V; j += lowbit(j))
                ++bit[i][j];
    }
    inline int sum(int x, int y) 
    {
        int ret = 0;
        for (int i = x; i; i -= lowbit(i))
            for (int j = y; j; j -= lowbit(j))
                ret += bit[i][j];
        return ret;
    }
    inline int query(int X1, int X2, int Y1, int Y2) { return sum(X2, Y2) - sum(X1 - 1, Y2) - sum(X2, Y1 - 1) + sum(X1 - 1, Y1 - 1); }
}
struct rec
{
    int X1, X2, Y1, Y2;
    rec(int x = 0, int y = 0) { X1 = X2 = x, Y1 = Y2 = y; }
    void add_pt(int x, int y) { X1 = std::min(X1, x), X2 = std::max(X2, x), Y1 = std::min(Y1, y), Y2 = std::max(Y2, y); }
    int area() const { return (X2 - X1) * (Y2 - Y1); }
    bool legal() const { return bit_2d::query(X1, X2, Y1, Y2) == 0; }
};
std::pair<int, int> pts[N];
int n, x, y, pcnt;
int ans_cnt, ans_area;
char op;
void pseudo_solve()
{
    std::shuffle(pts + 1, pts + pcnt + 1, rng);
    rec r = rec(pts[1].first, pts[1].second), tmp = r;
    int tmp_cnt = 1;
    for (int i = 2; i <= pcnt; ++i)
    {
        tmp.add_pt(pts[i].first, pts[i].second);
        (tmp.legal()) ? (r = tmp, ++tmp_cnt) : (tmp = r);
    }
    if (ans_cnt == tmp_cnt)
        ans_area = std::min(ans_area, r.area());
    else if (ans_cnt < tmp_cnt)
        ans_cnt = tmp_cnt, ans_area = r.area();
}
int main()
{
    // freopen("test.in", "r", stdin);
    double st = (double)clock();
    n = rd();
    while (n--)
    {
        x = rd() + 1, y = rd() + 1, op = rd_op();
        (op == 'G') ? ((void)(bit_2d::modify(x, y))) : ((void)(pts[++pcnt] = std::make_pair(x, y)));
    }
    ans_cnt = 1, ans_area = 0;
    while ((double)clock() - st < THRESHOLD * CLOCKS_PER_SEC)
        pseudo_solve();
    wr(ans_cnt), putchar('\n'), wr(ans_area);
}