topcoder SRM 566 Div2 1000

额,完了,这道topcoderDiv2把我按在地上摩擦。。。果然太菜了。。。

题意:

给你一个半径为R的圆,然后圆上等距离有n个木桩,木桩之间是等距离的,同时第一个木桩在(R,0)位置。然后这个平面上有一些点,你要用木桩围成一个圈把点都围住,问你最小面积。。。

输入:

  • n<222,r<100000,点数少于50个。。。

输出:

  • 最小面积。。。

分析:

已知,我们可以求出每一个木桩的位置,然后可以先用叉积判断是否可以把所有点围住,不然就输出-1,然后,我们就要使用区间DP了。。。

我们定义dp[i][j]表示从第i个木桩到第j个木桩的一条合法围栏最小面积,他保存的是此时的最小面积,转移就是枚举中间合法点更新。。。

代码:

vector X, Y;
double dp[250][250];
double Px[250], Py[250];
bool judge_line(double x1, double y1, double x2, double y2)
{
	for (int i = 0; i < X.size(); i++)
	{
		double x3 = X[i], y3 = Y[i];
		double flag = (x1 - x3) * (y2 - y1) - (x2 - x1) * (y1 - y3);
		if (flag < 0)
			return false;
	}
	return true;
}
double Mian(double x1, double y1, double x2, double y2, double x3, double y3)
{
	x1 -= x3;x2 -= x3;
	y1 -= y3;y2 -= y3;
	return (x1 * y2 - y1 * x2) / 2;
}
double FencingPenguinsEasy::calculateMinArea(int n, int r, vector x, vector y)
{
	X.clear(), Y.clear();
	for (int i = 0; i < 249; i++)
		for (int j = 0; j <= 249; j++)
			dp[i][j] = 0;
	double C = pi * 2 / n;
	for (int i = 0; i < x.size(); i++)
		X.push_back(x[i]);
	for (int i = 0; i < y.size(); i++)
		Y.push_back(y[i]);
	int siz = 0;
	for (int i = 0; i < n; i++)
		Px[++siz] = r * cos(C * i), Py[siz] = r * sin(C * i);
	for (int i = 2; i <= n; i++)
		if (!judge_line(Px[i - 1], Py[i - 1], Px[i], Py[i]))
			return -1.0;
	if (!judge_line(Px[siz], Py[siz], Px[1], Py[1]))
		return -1.0;


	for (int i = 1; i <= siz; i++)
		for (int j = 1; j <= siz; j++)
			if (i == j) dp[i][j] = 0;
			else dp[i][j] = inf;
	for (int i = 2; i = 1; j--)
			for (int k = j + 1; k <= i; k++)
				if (judge_line(Px[j], Py[j], Px[k], Py[k]))
					dp[j][i] = min(dp[j][i], dp[k][i] + fabs(Mian(Px[k], Py[k], Px[j], Py[j], Px[i], Py[i])));
	double ans = inf;
	for (int i = 1; i <= siz; i++)
		for (int j = i + 2; j <= siz; j++)
			if (judge_line(Px[j], Py[j],Px[i], Py[i]))
				ans = min(ans, dp[i][j]);
	return ans;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注