JOI 春合宿 2008-day4 Ruins

問題文 : 最古の遺跡2

解法 :

dp[i][j] : 辺ij を最後に使った時の頂点数の最大値, とする. このとき, 以下のような図を考える.

ここで, 現在赤の辺から水色の辺に遷移しようと考えていたとすると, 赤の辺と水色の辺のなす角θが180 度以下であれば, dp[水色の辺] = max(dp[水色の辺], dp[赤色の辺] + 1) とすることができる (☆印の点が新たに追加されたと考えることが可能であるため.

ある点をかならず頂点群に入っていると仮定し, 角度でソートして, 自分より下の点は使わないとして良い. (前で計算済みであるはずなので

必ず入っている頂点の決め打ちにO(N), 辺の遷移のために必要な点の列挙にO(N^3) かかるので, O(N^4) 時間でこの問題を解く事ができる.

コード :

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

using namespace std;

struct Point {
	int x, y;
	Point(int x, int y) : x(x), y(y) {}
	Point(){}
} p[129];

bool ccw(Point a, Point b)
{
	if (a.x * b.y - a.y * b.x < 0) return (false);
	return (true);
}

bool operator < (const Point &a, const Point &b)
{
	return (ccw(Point(a.x - p[128].x, a.y - p[128].y), Point(b.x - p[128].x, b.y - p[128].y)));
}

int N;
int memo[129][129];
int main()
{
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++)
		scanf("%d %d", &p[i].x, &p[i].y);
	
	int res = 0;
	
	for (int idx = 0; idx < N; idx++){
		vector<Point> v;
		for (int i = 0; i < N; i++){
			if (p[idx].x < p[i].x || (p[idx].x == p[i].x && p[idx].y < p[i].y))
				v.push_back(p[i]);
		}
		p[128] = p[idx];
		sort(v.begin(), v.end());
		
		int M = v.size();
		
		memset(memo, 0, sizeof(memo));
		for (int i = 0; i < M; i++)
			memo[128][i] = 2;
		
		for (int i = -1; i < M; i++){
			int piv = ~i ? i : 128;
			Point a = piv & 128 ? p[128] : v[i];
			for (int j = i + 1; j < M; j++){
				res = max(res, memo[piv][j]);
				for (int k = j + 1; k < M; k++){
					if (!ccw(Point(a.x - v[j].x, a.y - v[j].y), Point(v[k].x - v[j].x, v[k].y - v[j].y))){
						memo[j][k] = max(memo[j][k], memo[piv][j] + 1);
					}
				}
			}
		}
	}
	
	printf("%d\n", res);
	
	return (0);
}