uva 10641 - Barisal Stadium(dp+幾何)

題目鏈接：uva 10641 - Barisal Stadium

題目大意：按照順時針給出操場的周邊點，然後給出周圍可以建設照明燈的位置，以及在該位置建設照明燈的代價，照明燈照射的范圍與操場的邊界相切，現在要求一個最小的花費，要求操場的所有邊都被照射到。

解題思路：dp[i][j]表示從第i個點到第j個點之間的邊都被照射到的最小代價，這樣轉移方程也很好寫，只要有某個等得照射范圍有覆蓋到i，j，就可以向外擴展。

然而現在最主要的問題是如何求各個點的照射范圍，一開始我是用燈的位置和邊界所有點求斜率，最大的作為左邊界，最小的作為右邊界，但是WA，後來發現這種做法根本沒有科學依據，無奈幾何不行，參考了別人的題解。是這樣做的：先求出操場的中心，然後每條操場的邊，如果等和中心位於這條邊的同一側，那麼是不能照射的，否側是可以照射的。

還有，在處理環的時候，我將數組直接擴大兩倍。

#include 
#include 
#include 
#include 

using namespace std;
const int N = 105;
const int M = 1005; 
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const double pi = atan(1.0)*4;

struct state {
	int l, r, val;	
}s[M];

struct point {
	double x, y;
	point (double x = 0, double y = 0) { this->x = x; this->y = y;}
	point operator - (const point &o) const {return point(x - o.x, y - o.y);}
	double det(const point &o) const {return x * o.y - y * o.x;}
}p[N], o;
int n, m, dp[N];

inline double dis(double x, double y) {
	return sqrt(x*x+y*y);
}

inline int sign(double x) {return x < -eps ? -1 : x > eps;}

inline double getP(double y, double x) {
	if (fabs(x) < eps) {
		return y > 0 ? -pi : pi;
	}
	return atan2(y, x);
}

bool judge (point l, point a, point b) {
	return sign((l - a).det(b - a) * (o - a).det(b - a)) < 0;
}

void cat (state& u, double xi, double yi) {
	bool flag[N];
	memset(flag, false, sizeof(flag));

	for (int i = 0; i < n; i++) {
		if (judge(point(xi, yi), p[i], p[i+1]))
			flag[i] = true;
	}

	if (flag[0] && flag[n-1]) {
		int l = n-1, r = n;
		while (flag[l]) u.l = l, l--;
		while (flag[r-n]) u.r = r, r++;
		
	} else {
		int l = 0, r = n-1;
		while (!flag[l]) l++;
		u.l = l;
		while (!flag[r]) r--;
		u.r = r;
	}

	u.r++;
	if (u.r < u.l)
		u.r += n;
}	

void init () {

	o.x = o.y = 0;
	for (int i = 0; i < n; i++) {
		scanf("%lf%lf", &p[i].x, &p[i].y);
		o.x += p[i].x;
		o.y += p[i].y;
	}
	o.x /= n;
	o.y /= n;

	p[n] = p[0];
	double x, y;
	int value;

	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%lf%lf%d", &x, &y, &value);
		cat(s[i], x, y);
		s[i].val = value;
	}
}

bool solve () {
	int ans = INF;

	for (int i = 0; i < n; i++) {
		memset(dp, INF, sizeof(dp));
		dp[i] = 0;

		for (int j = 0; j < n; j++) {

			int t = i + j;
			for (int x = 0; x < m; x++) {
				if (s[x].l > t)
					continue;

				int ad = min(s[x].r, i+n);
				dp[ad] = min(dp[ad], dp[t]+s[x].val);
			}
		}
		ans = min(ans, dp[i+n]);
	}

	if (ans == INF)
		return false;
	printf("%d\n", ans);
	return true;
}

int main () {
	while (scanf("%d", &n) == 1 && n) {
		init ();
		if (!solve())
			printf("Impossible.\n");
	}
	return 0;
}