TIOJ::1263 . 保加利亞的多邊形

http://tioj.ck.tp.edu.tw/problems/1263

很有趣的爆搜題。給你一些點，求最小的凸K邊形面積。


題目給你50個點，K不超過10，感覺就很爆搜對吧。

C50取10有點多，不過我們觀察一下發現凸多邊形，必須要滿足邊永遠是逆時針轉的，這樣就少很多點了。
再來就是，除了起點和第二個點之外，每個點都要符合「前一個點到自己到起點」是逆時針，還有「自己到起點到第二個點」也是逆時針(一開始少加了這種情況QQ，WA了一次)，這樣就能保證搜出來的多邊形是凸多邊形了。

因為上面的條件，我們可以把凸多邊形切成很多塊三角形，我們可以依序把這些三角形面積加起來，求出總面積，為了防止誤差，我們都先算兩倍面積(用測量員公式，只要整數座標，兩倍面積就不會出現小數)。

最後，在加個上限減枝就可以輕鬆AC了。
上限剪枝就是用現在最佳解限制爆搜，如果現在累積的面積已經超過目前最佳解了，那就剪掉。

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=(l);i<(n);i++)
using namespace std;
const int N = 51, MAX = 2147483647;
typedef pair<int,int> PII;
PII D[N];
int n,m,ans;
bool wed[N];
inline PII operator-(PII a,PII b){
    return PII(a.first-b.first,a.second-b.second);
}
inline int cross(PII a,PII b){
    return a.first*b.second - b.first*a.second;
}
inline int triangle_area(PII a,PII b,PII c){
    return abs(cross(a,b)+cross(b,c)+cross(c,a));
}
void DFS(int area,int pre,int x,int k,int fs,int sd){
    // if(k==1&&area==3)cout<<area<<endl;
    if(area>=ans)return;
    if(k>=m-1);
    else if(cross(D[x]-D[pre],D[fs]-D[x])<0)return;
    else if(cross(D[fs]-D[x],D[sd]-D[fs])<0)return;
    else if(k==1){
        ans = min(ans,area);
        return;
    }
    F(n)if(!wed[i]){
        if(k==m||cross(D[x]-D[pre],D[i]-D[x])>0){
            wed[i]=true;
            int tmp = area + (k==m?0:triangle_area(D[fs],D[x],D[i]));
            if(k==m)sd = i;
            DFS(tmp,x,i,k-1,fs,sd);
            wed[i]=false;
        }
    }
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    F(n)cin>>D[i].first>>D[i].second;
    ans = MAX;
    F(n){
        wed[i] = true;
        DFS(0,-1,i,m,i,-1);
        wed[i] = false;
    }
    cout<<(ans==MAX?0:(ans>>1))<<'\n';
    // cout<<flush;
    // while(1);
}