PCK 2013 予選問9 - ハッピーエンド問題

問題文 :

平面上に与えられた$N$ 個の点から, ちょうど$k$ 個の点を結んでできる凸多角形のうち、最も面積の小さいものを見つけるプログラムを作成せよ. ただし, $N$ 個の点の座標を与えられた後, 質問として凸多角形の角の個数$k$ がいくつか与えられる.

$N \leqq 40$, $k \leqq 40$
座標は整数値, $|x_i, \ y_i| \leqq 10^5$

解法 :
dp[i][j][k][l] : i 個の点からなる多角形で, 点j が始点, 点k が最後から2 番目に使った点, 点k が最後に使った点のときの最小値, としてdp. JOI 春のruins2 に雰囲気が似ている.

復元はprev[i][j][k][l] みたいな配列があれば出来る.

コード :

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long lint;

const lint INF = 1001001001001001001;

class Point {
	public:
	int x, y, id;
	Point(int x = 0, int y = 0, int id = 0) : x(x), y(y), id(id){}
	Point operator - (Point p){ return Point (x - p.x, y - p.y);}
};

int cross(Point a, Point b)
{
	return (a.x * b.y - a.y * b.x);
}

Point p;

bool sortT(Point a, Point b)
{
	return (cross(a - p, b - p) > 0);
}

vector<Point> normalize(vector<Point> &v)
{
	int pt = 0;
	for (int i = 1; i < v.size(); i++){
		if (v[pt].y > v[i].y || (v[pt].y == v[i].y && v[pt].x > v[i].x)){
			pt = i;
		}
	}
	swap(v[pt], v[0]);
	p = v[0];
	sort(v.begin() + 1, v.end(), sortT);
	return (v);
}

int area(Point a, Point b, Point c)
{
	return (abs(cross(c - a, b - a)));
}

lint dp[41][41][41][41];
int prev[41][41][41][41];

int main()
{
	int N, Q;
	
	scanf("%d", &N);
	
	vector<Point> v;
	for (int i = 0; i < N; i++){
		Point t;
		t.id = i;
		scanf("%d %d", &t.x, &t.y);
		v.push_back(t);
	}
	
	for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) for (int k = 0; k <= N; k++) for (int l = 0; l <= N; l++)
		dp[i][j][k][l] = INF;
	
	for (int i = 0; i < N; i++){
		vector<Point> v2;
		for (int j = 0; j < N; j++){
			if (v[i].x < v[j].x || (v[i].x == v[j].x && v[i].y < v[j].y)){
				v2.push_back(v[j]);
			}
		}
		
		p = v[i];
		sort(v2.begin(), v2.end(), sortT);
		
		for (int j = 0; j < v2.size(); j++){
			for (int k = j + 1; k < v2.size(); k++){
				dp[3][i][v2[j].id][v2[k].id] = area(v[i], v2[j], v2[k]);
			}
		}
		
		for (int j = 4; j <= N; j++){
			for (int k = 0; k < v2.size(); k++){
				for (int l = k + 1; l < v2.size(); l++){
					for (int m = 0; m < k; m++){
						if (cross(v2[k] - v2[m], v2[l] - v2[m]) > 0 && dp[j][i][v2[k].id][v2[l].id] > dp[j - 1][i][v2[m].id][v2[k].id] + area(v[i], v2[k], v2[l])){
							dp[j][i][v2[k].id][v2[l].id] = dp[j - 1][i][v2[m].id][v2[k].id] + area(v[i], v2[k], v2[l]);
							prev[j][i][v2[k].id][v2[l].id] = v2[m].id;
						}
					}
				}
			}
		}
	}
	
	scanf("%d", &Q);
	
	for (int i = 0; i < Q; i++){
		int num;
		scanf("%d", &num);
		
		int piv1, piv2, piv3;
		lint ans = INF;
		for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) for (int l = 0; l < N; l++){
			if (dp[num][j][k][l] < ans){
				ans = dp[num][j][k][l];
				piv1 = j; piv2 = k; piv3 = l;
			}
		}
		
		if (ans == INF) printf("NA\n");
		else {
			vector<Point> res;
			while (num != 3){
				res.push_back(v[piv3]);
				int t = prev[num][piv1][piv2][piv3];
				num--;
				piv3 = piv2;
				piv2 = t;
			}
			res.push_back(v[piv3]); res.push_back(v[piv2]); res.push_back(v[piv1]);
			res = normalize(res);
			for (int i = 0; i < res.size(); i++) printf("%d%c", res[i].id + 1, " \n"[i == res.size() - 1]);
		}
	}
	
	return (0);
}