记录编号	590047	评测结果	AAAAAAA
题目名称	[NOIP 2002]矩形覆盖	最终得分	100
用户昵称	liuyiche	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2024-07-09 15:05:26	内存使用	0.84 MiB

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

typedef long long ll;
typedef pair<int,int> P;

int n, k, Min = 1e9;
vector<P> v(55);
int p[6];
int Minx[6];
int Miny[6];
int Maxx[6];
int Maxy[6];

inline bool Iscover(int a, int b)
{
    if(Maxx[a] >= Minx[b] && Maxy[a] >= Miny[b] && Maxx[a] <= Maxx[b] && Maxy[a] <= Maxy[b])
        return true;
    if(Maxx[b] >= Minx[a] && Maxy[b] >= Miny[a] && Maxx[b] <= Maxx[a] && Maxy[b] <= Maxy[a])
        return true;
    if(Maxx[a] >= Minx[b] && Miny[a] >= Miny[b] && Maxx[a] <= Maxx[b] && Miny[a] <= Maxy[b])
        return true;
    if(Maxx[b] >= Minx[a] && Miny[b] >= Miny[a] && Maxx[b] <= Maxx[a] && Miny[b] <= Maxy[a])
        return true;
    if(Minx[a] >= Minx[b] && Maxy[a] >= Miny[b] && Minx[a] <= Maxx[b] && Maxy[a] <= Maxy[b])
        return true;
    if(Minx[b] >= Minx[a] && Maxy[b] >= Miny[a] && Minx[b] <= Maxx[a] && Maxy[b] <= Maxy[a])
        return true;
    if(Minx[a] >= Minx[b] && Miny[a] >= Miny[b] && Minx[a] <= Maxx[b] && Miny[a] <= Maxy[b])
        return true;
    if(Minx[b] >= Minx[a] && Miny[b] >= Miny[a] && Minx[b] <= Maxx[a] && Miny[b] <= Maxy[a])
        return true;
    return false;
}

inline void dfs(int step, int cnt)
{
    if(cnt >= Min)
        return;
    if(step == n+1)
    {
        bool flag = true;
        for(int i = 1; i < k; ++i)
            for(int j = i+1; j <= k; ++j)
                if(Iscover(i,j) == true)
                {
                    flag = false;
                    break;
                }
        if(flag == true)
        for(int i = 1; i <= k; ++i)
            if(p[i] == 0)
            {
                flag = false;
                break;
            }
        if(flag == true)
            Min = min(Min,cnt);
        return;
    }
    bool flag = false;
    for(int i = 1; i <= k; ++i)
    {
        if(v[step].first >= Minx[i] && v[step].first <= Maxx[i] && v[step].second >= Miny[i] && v[step].second <= Maxy[i])
        {
            p[i]++;
            dfs(step+1,cnt);
            p[i]--;
            flag = true;
            break;
        }
    }
    if(flag == false)
    for(int i = 1; i <= k; ++i)
    {
        int tmp1 = Minx[i], tmp2 = Miny[i], tmp3 = Maxx[i], tmp4 = Maxy[i];
        int tt = cnt-(Maxx[i]-Minx[i])*(Maxy[i]-Miny[i]);
        p[i]++;
        if(tmp1 == -1)
        {
            Minx[i] = v[step].first;
            Miny[i] = v[step].second;
            Maxx[i] = v[step].first;
            Maxy[i] = v[step].second;
        }
        else
        {
            Minx[i] = min(Minx[i],v[step].first);
            Miny[i] = min(Miny[i],v[step].second);
            Maxx[i] = max(Maxx[i],v[step].first);
            Maxy[i] = max(Maxy[i],v[step].second);
        }
        tt += (Maxx[i]-Minx[i])*(Maxy[i]-Miny[i]);
        dfs(step+1,tt);
        p[i]--;
        Minx[i] = tmp1;
        Miny[i] = tmp2;
        Maxx[i] = tmp3;
        Maxy[i] = tmp4;
    }
}
    
int main()
{
    freopen("jxfg.in", "r", stdin);
    freopen("jxfg.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    memset(Minx,-1,sizeof(Minx));        
    memset(Miny,-1,sizeof(Miny));  
    memset(Maxx,-1,sizeof(Maxx));        
    memset(Maxy,-1,sizeof(Maxy));  
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> v[i].first >> v[i].second;
    
    dfs(1,0);
    
    cout << Min;
    
   	return 0;
}