uvalive 6902 Three Squares

标签： 二分 搜索

---

题目描述

戳这里
题目大意：给你n个点，请确定正方形的最小边长使得用三个这样的正方形可以覆盖n个点

题解

首先可以发现答案具有单调性，可以二分答案正方形边长$len$，然后就是怎么验证的问题了（考场写了个假贪心浪费半小时)这里题解直接用的搜索，即枚举当前剩余点，确定左上角，右上角，左下角，右下角，那么当前正方形肯定会放在这四个角之一，然后递归搜索即可。复杂度大约为$O(64*nlog(n))$
注意回溯时候要取消当前覆盖的点。

代码

#include<bits/stdc++.h>
#define N 100010
using namespace std;

int n, l, r;
int re[N];
bool vis[N];
struct node{
    int x, y;
}p[N];

void getmax(int &x, int &y)
{
    int a = -1e9, b = -1e9;
    for(int i = 1; i <= n; i ++)
    {
        if(vis[i]) continue;
        if(a < p[i].x) a = p[i].x;
        if(b < p[i].y) b = p[i].y;
    }
    x = a; y = b;
}

void getmin(int &x, int &y)
{
    int a = 1e9, b = 1e9;
    for(int i = 1; i <= n; i ++)
    {
        if(vis[i]) continue;
        if(a > p[i].x) a = p[i].x;
        if(b > p[i].y) b = p[i].y;
    }
    x = a; y = b;
}

void modify(int x, int y, int xx, int yy, int cnt, int &tot)
{
    for(int i = 1; i <= n; i ++)
        if(!vis[i] && x <= p[i].x && y <= p[i].y)
            if(p[i].x <= xx && p[i].y <= yy)
                vis[i] = 1, tot ++, re[cnt + tot] = i;
    /*
    printf("%d %d", l, r); system("pause");
    if(((l + r) >> 1) == 1)
    {
        printf("%d %d", cnt, tot); system("pause");
        for(int i = cnt + 1; i <= cnt + tot; i ++)
            printf("%d %d\n", p[re[i]].x, p[re[i]].y);
        system("pause");
    }
    */

}

void cancel(int st, int ed)
{
    for(int i = st + 1; i <= ed; i ++)
        vis[re[i]] = 0;
}

bool dfs(int l, int c, int cnt)
{
    if(c > 3)
    {
        int cnt = 0;
        for(int i = 1; i <= n; i ++)
            if(vis[i]) cnt ++;
        return (cnt == n);
    }
    int tot = 0;
    int dx, dy; getmax(dx, dy);
    int ddx, ddy; getmin(ddx, ddy);
    //printf("l=%d c=%d cnt=%d", l, c, cnt); system("pause");
    //for(int i = 1; i <= n; i ++)
    //    if(vis[i]) printf("%d %d\n", p[i].x, p[i].y);
    //system("pause");
    //左下角
    modify(ddx, ddy, ddx + l, ddy + l, cnt, tot);
    if(dfs(l, c + 1, cnt + tot)) return true;
    cancel(cnt, cnt + tot); tot = 0;
    //左上角
    modify(ddx, ddy - l, ddx + l, ddy, cnt, tot);
    if(dfs(l, c + 1, cnt + tot)) return true;
    cancel(cnt, cnt + tot); tot = 0;
    //右下角
    modify(dx - l, ddy, dx, ddy + l, cnt, tot);
    if(dfs(l, c + 1, cnt + tot)) return true;
    cancel(cnt, cnt + tot); tot = 0;
    //右上角
    modify(dx - l, dy - l, dx, dy, cnt, tot);
    if(dfs(l, c + 1, cnt + tot)) return true;
    cancel(cnt, cnt + tot); tot = 0;

    return false;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++)
            scanf("%d%d", &p[i].x, &p[i].y);
        l = 0, r = 2e9;
        //dfs(1, 1, 0);
        while(l < r)
        {
            memset(vis, false, sizeof(vis));
            int mid = (l + r) >> 1;
            if(dfs(mid, 1, 0)) r = mid;
            else l = mid + 1;
        }
        printf("%d\n", r);
    }
    return 0;
}