TopCoder SRM679(Div.1) Normal RedAndBluePoints

Posted on By 二价氢

题目大意

给定50个红点和50个蓝点,三点不共线,求一个不包含红点的多边形最多能包含多少蓝点

解法

我们分下面几步来完成这个算法,首先,我们知道答案肯定是一个由蓝点组成的凸包

一、计算每个三角形包含了多少个蓝点与红点,这一步可以用\(O(n^4)\)的枚举实现

二、用动态规划的方法求凸包,这一步也可以用\(O(n^4)\)的枚举实现,用\(f_{i,j,k}\)表示最左端为第i个蓝点,次右端为第j个蓝点,最右端为第k个蓝点组成的上/下凸包的答案,显然,转移方程就是\(f_{i,k,l} = f_{i,j,k} + s_{i,k,l}\),其中\(s_{i,k,l}\)表示三角形\(\Delta_{i,k,l}\)包含的蓝点数。

将步骤二执行两遍,求出上凸包和下凸包对应的答案,最后再用\(O(n^4)\)的枚举合并即可。

###Code

typedef pair<int, int> pii;
#define x first
#define y second
const int maxn = 55;
class RedAndBluePoints {
public:
	int inner[maxn][maxn][maxn];
	int upb[maxn][maxn], upr[maxn][maxn];
	int innerb[maxn][maxn][maxn], innerr[maxn][maxn][maxn];
	int dp1[maxn][maxn][maxn], dp2[maxn][maxn][maxn];
	vector<pii> bl, rd;
	int cross(const pii &a, const pii &b) {
		return a.x * b.y - a.y * b.x;
	}
	pii _(const pii &a, const pii &b) {return pii(a.x - b.x, a.y - b.y);}
	bool isinner(const pii &a, const pii &b, const pii &c, const pii &q) {
		return (q != a && q != b && q != c && 
		cross(_(q, a), _(b, a)) >= 0 && cross(_(q, b), _(c, b)) >= 0 && cross(_(q, c), _(a, c)) >= 0);
	}
	int eabs(const int &x) {return x < 0 ? -x : x;}
	int find(vector <int> blueX, vector <int> blueY, vector <int> redX, vector <int> redY) {
		int b = blueX.size(), r = redX.size();
		int ans = min(2, b);
		memset(inner, 0, sizeof(inner));memset(upb, 0, sizeof(upb));memset(upr, 0, sizeof(upr));
		memset(innerb, 0, sizeof(innerb));memset(innerr, 0, sizeof(innerr));
		memset(dp1, -1, sizeof(dp1));memset(dp2, -1, sizeof(dp2));
		for (int i = 0; i < b; i++) bl.push_back(pii(blueX[i], blueY[i]));
		for (int i = 0; i < r; i++) rd.push_back(pii(redX[i], redY[i]));
		sort(bl.begin(), bl.end());
		for (int i = 0; i < b; i++)
		for (int j = i + 1; j < b; j++)
		for (int k = 0; k < b; k++)
			if (cross(_(bl[k], bl[i]), _(bl[j], bl[i])) > 0) {
				for (int l = 0; l < b; l++)
					innerb[i][j][k] += isinner(bl[i], bl[j], bl[k], bl[l]);
				for (int l = 0; l < r; l++)
					innerr[i][j][k] += isinner(bl[i], bl[j], bl[k], rd[l]);
				if(innerr[i][j][k] == 0)
					ans = max(ans, dp1[i][j][k] = dp2[i][k][j] = innerb[i][j][k] + 3);
			}
		for (int i = 0; i < b; i++)
		for (int j = i + 1; j < b; j++)
		for (int k = j + 1; k < b; k++)
		for (int l = k + 1; l < b; l++)
			if (innerr[i][k][l] == 0 && cross(_(bl[l], bl[i]), _(bl[k], bl[i])) > 0 && cross(_(bl[l], bl[j]), _(bl[k], bl[j])) > 0)
				dp1[i][k][l] = max(dp1[i][k][l], dp1[i][j][k] + innerb[i][k][l] + 1), ans = max(ans, dp1[i][k][l]);
		for (int i = 0; i < b; i++)
		for (int j = i + 1; j < b; j++)
		for (int k = j + 1; k < b; k++)
		for (int l = k + 1; l < b; l++)
			if (innerr[i][l][k] == 0 && cross(_(bl[l], bl[i]), _(bl[k], bl[i])) < 0 && cross(_(bl[l], bl[j]), _(bl[k], bl[j])) < 0)
				dp2[i][k][l] = max(dp2[i][k][l], dp2[i][j][k] + innerb[i][l][k] + 1), ans = max(ans, dp2[i][k][l]);
		for (int i = 0; i < b; i++)
		for (int j = i + 1; j < b; j++)
		for (int k = i + 1; k < j; k++)
		for (int l = i + 1; l < j; l++)
			if (k != l)
		    	ans = max(ans, dp1[i][k][j] + dp2[i][l][j] - 2);
		return ans;
	}
};

Level Upper 2016 - TopCoder 500 : 2 / 5