SRM 566 Div2 Hard FencingPenguinsEasy

解法

あるフェンスが利用可能である条件は、フェンスを張ったときに左右のどちらか一方のみにペンギンが存在するような場合である。（ここでは、反時計回りにフェンスを張っていくので、左側に全てのペンギンがいる場合に利用可能とする。）

利用可能であるフェンスのみを用いて囲った時の面積を最小化にする方法を考える。
フェンスを張り始める杭を決める。この杭をstartとすると、フェンスを貼り終える杭もstartである。区別のためstart'とする。
i -> jにフェンスを張った時の面積の増加分は三角形(start, i, j)の面積で求められる。
区間[start, i]と区間[i, start']のフェンスの張り方は面積に相互作用しないので、区間[start, i]のフェンスの張り方を決定するときは、面積が最小となるものを選べば良い。よって、以下のdpを解けばいい。
dp[i] = [start, i]にフェンスを張った時の最小の面積として、
dp[j] = min{ dp[i] + triangle_area(start, i, j); フェンスi -> jは利用可能 }
求めたい解: dp[start'] = startから張り始めたときの最小の面積

以上のdpを全ての杭をstartとして計算し、その中で最小のものを全体の解とする。

幾何的な要素は外積を使うと楽

ソースコード

const double PI = acos(-1.0);

double cross(double x1, double y1, double x2, double y2)
{
    return x1 * y2 - y1 * x2;
}
double tri_area(double x1, double y1, double x2, double y2, double x3, double y3)
{
    return abs(cross(x2 - x1, y2 - y1, x3 - x1, y3 - y1)) / 2;
}
double FencingPenguinsEasy::calculateMinArea(int numPosts, int radius, vector <int> x, vector <int> y)
{
    const double sp = 2 * PI / numPosts;

    double px[300], py[300];
    rep(i, numPosts)
    {
	px[i] = radius * cos(i * sp);
	py[i] = radius * sin(i * sp);
    }

    bool can_connect[300][300];	// i -> j
    rep(i, numPosts) rep(j, numPosts)
    {
	// ok if all penguins in left
	can_connect[i][j] = i != j;
	rep(k, x.size())
	{
	    // (post(i) -> post(j)) * (post(i) -> pen(k)) < 0
	    if (cross(px[j] - px[i], py[j] - py[i], x[k] - px[i], y[k] - py[i]) < 0)
	    {
		can_connect[i][j] = false;
		break;
	    }
	}
    }

    const double inf = 1e60;
    double res = inf;
    rep(start, numPosts)
    {
	double dp[333]; // [start, i] -> min area
	rep(i, numPosts)
	    dp[i] = can_connect[start][i] ? 0 : inf;

#define next(i) (((i) + 1) % numPosts)
	for (int i = next(start); i != start; i = next(i))
	{
	    for (int j = i + 1; j != i; j = next(j))
		if (can_connect[i][j])
		    chmin(dp[j], dp[i] + tri_area(px[start], py[start], px[i], py[i], px[j], py[j]));
	}
	chmin(res, dp[start]);
    }
    return res == inf ? -1 : res;
}