Description

在笛卡尔平面上给出了n个点。现在，你必须使用一些矩形，其两侧是平行的轴，以掩盖他们。每一点都必须覆盖。一个点可以被几个矩形覆盖。每个矩形应该包括至少两个点，包括那些落在它的边界上的点。矩形应具有整体尺寸。退化的情况下（矩形与零区）是不允许的。你将如何选择矩形，从而最大限度地减少他们的总面积？

输入

输入由几个测试用例组成。每个测试用例都从包含单个整数的一行开始。n(2≤)n≤15)。下一个n行包含两个整数x, y(−1,000≤x, y≤1,000)，给出点的坐标。假定没有两点是相同的。最后一个测试用例中只有一个零。

输出

为每个测试用例在单独的行上输出矩形的最小总面积。

样本输入

2
0 1
1 0
0

样本输出

1

题解

状压dp
先预处理出所有的矩形，有n*(n-1)/2个。

然后将每个矩形所涵盖的点也处理出来。

dp[s]表示矩形覆盖点集合为 s 的时候的最小面积

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;

const int N=20,M=120;
struct Node
{
    int s;
    int area;
}a[M];
PII p[N];
int f[1<<15];
int n;
int cnt;

inline int calc(PII a,PII b)
{
    int l=max(1,abs(a.first-b.first));
    int w=max(1,abs(a.second-b.second));
    return l*w;
}

inline bool check(PII a,PII b,PII c)
{
    return (a.first-c.first)*(b.first-c.first)<=0 && (a.second-c.second)*(b.second-c.second)<=0;
}

void init()
{
    cnt=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            Node t;
            t.s=0;
            t.area=calc(p[i],p[j]);
            t.s |= 1<<i,t.s |= 1<<j;

            for(int k=0;k<n;k++)
                if(check(p[i],p[j],p[k]))
                    t.s |= 1<<k;
            a[++cnt]=t;
        }
}

void print()
{
    for(int i=1;i<=cnt;i++)
    {
        cout<<bitset<6>(a[i].s)<<' '<<a[i].area<<endl;
    }
}

int main()
{
    while(cin>>n && n)
    {
        int x,y;
        for(int i=0;i<n;i++) cin>>p[i].first>>p[i].second;

        init();

        //print();

        memset(f,0x3f,sizeof f);
        f[0]=0;

        for(int s=0;s<(1<<n);s++)
            for(int i=1;i<=cnt;i++)
                f[s|a[i].s]=min(f[s|a[i].s],f[s]+a[i].area);
        cout<<f[(1<<n)-1]<<endl;
    }
    // system("pause");
}