首页 > 代码库 > uva 10641 - Barisal Stadium(dp+几何)
uva 10641 - Barisal Stadium(dp+几何)
题目链接:uva 10641 - Barisal Stadium
题目大意:按照顺时针给出操场的周边点,然后给出周围可以建设照明灯的位置,以及在该位置建设照明灯的代价,照明灯照射的范围与操场的边界相切,现在要求一个最小的花费,要求操场的所有边都被照射到。
解题思路:dp[i][j]表示从第i个点到第j个点之间的边都被照射到的最小代价,这样转移方程也很好写,只要有某个等得照射范围有覆盖到i,j,就可以向外扩展。
然而现在最主要的问题是如何求各个点的照射范围,一开始我是用灯的位置和边界所有点求斜率,最大的作为左边界,最小的作为右边界,但是WA,后来发现这种做法根本没有科学依据,无奈几何不行,参考了别人的题解。是这样做的:先求出操场的中心,然后每条操场的边,如果等和中心位于这条边的同一侧,那么是不能照射的,否侧是可以照射的。
还有,在处理环的时候,我将数组直接扩大两倍。
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。