PCK2013 予選 9

幾何ライブラリなくて焦ったけど大丈Vだった。

左端の取る点を固定して、反時計回りに取っていく。
dp[今までの頂点数][二つ前の頂点][一つ前の頂点]=面積最小値
とすると頑張って更新できる。O(N^5)
この値から、すべての答えをあらかじめ求めておく。
出力の順番を勘違いしてたので、ちょっと終盤頭悪いことになってます

#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<cstring>
#include<cstdio>
#include<complex>
 
#define REP(i,m) for(int i=0;i<m;++i)
#define REPN(i,m,in) for(int i=in;i<m;++i)
#define ALL(t) (t).begin(),(t).end()
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
 
#define prl cerr<<__LINE__<<" is called"<<endl
#define dump(x) cerr<<#x<<" = "<<x<<endl
 
using namespace std;
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
typedef pair<int,int> pi;
typedef long long lint;
typedef complex<lint> P;
const lint INF2=1e18;
 
P p[50],q[50];
int n;
bool cmp(const P& a,const P& b){
    if(a.real()!=b.real()) return a.real()<b.real();
    return a.imag()<b.imag();
}
lint cross(P a,P b){
    return a.real()*b.imag()-a.imag()*b.real();
}
int ccw(P a,P b,P c){
    b-=a;c-=a;
    if(cross(b,c)<0) return -1;//clockwise
    if(cross(b,c)>0) return 1;//counter-clockwise
    return 0;
}
 
lint getarea(P a,P b,P c){
    return abs(cross(b-a,c-a));
}
 
 
int id[55],rev[55];
lint minarea[55];
vector<int> vs[55];
lint dp[55][55][55];
int back[55][55][55];
void solve(int n,int add){
    REP(i,n+1) REP(j,n+1) REP(k,n+1) dp[i][j][k]=INF2;
    REPN(i,n,1) {
        dp[2][0][i]=0;
    }
 
    REP(i,n+1) REP(j,n) REP(k,n) if(dp[i][j][k]<INF2){
        REPN(l,n,1) if(j!=l && k!=l){
            if(ccw(q[j],q[k],q[l])==1 && ccw(q[k],q[l],q[0])>=0){
            lint nval=dp[i][j][k]+getarea(q[0],q[k],q[l]);
            if(dp[i+1][k][l]>nval){
                dp[i+1][k][l]=nval;
                back[i+1][k][l]=j;
            }
            }
        }
        if(minarea[i]>dp[i][j][k]){
            vector<int> tmp;
            tmp.pb(rev[k+add]);
            tmp.pb(rev[j+add]);
            int k2=k,j2=j,i2=i;
            while(j2!=0){
                int last=back[i2][j2][k2];
                k2=j2;
                j2=last;
                tmp.pb(rev[j2+add]);
                --i2;
            }
 
            minarea[i]=dp[i][j][k];
            reverse(ALL(tmp));
            vs[i]=tmp;
        }
    }
 
 
}
 
P prev[55];
int main(){
    cin>>n;
    REP(i,n) cin>>p[i].real()>>p[i].imag(),q[i]=prev[i]=p[i];
    REP(i,n+1) minarea[i]=INF2;
 
    sort(p,p+n,cmp);
    REP(i,n){
        REP(j,n) if(q[i]==p[j]) id[i]=j;
    }
    REP(i,n) rev[id[i]]=i;
    REP(i,n){
        REPN(j,n,i) q[j-i]=p[j]-p[i];
 
        solve(n-i,i);
    }
     
    REPN(s,n+1,3) if(minarea[s]!=INF2){
        REP(i,s){
            int fail=0;
            REP(j,s) if(prev[vs[s][i]].imag()>prev[vs[s][j]].imag() 
            || (prev[vs[s][i]].imag()==prev[vs[s][j]].imag() &&
                    prev[vs[s][i]].real()>prev[vs[s][j]].real())){
                fail=1;
            }
            if(!fail){
                rotate(vs[s].begin(),vs[s].begin()+i,vs[s].end());
                break;
            }
        }
    }
 
    int q;cin>>q;
    REP(hoge,q){
        int m;cin>>m;
        if(minarea[m]==INF2){
            puts("NA");
        }else{
            REP(j,m) printf("%d%c",vs[m][j]+1,j==m-1?'\n':' ');
        }
    }
 
    return 0;
}