首页 > 代码库 > uva 10641 (来当雷锋的这回....)
uva 10641 (来当雷锋的这回....)
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const double eps = 1e-6; const int inf = 0x3f3f3f3f; int n,m; int f[100]; struct point{ double x,y; point(double xx = 0,double yy = 0){ this->x = xx; this->y = yy; } void read(){ scanf("%lf%lf",&x,&y); } }p[100]; struct Q{ int l,r,c; }q[1005]; bool judge(point pp,point p1,point p2){///向量叉积!判断顺逆时针时注意三个点的先后位置 /// <0是就是第一个向量在第二个向量的逆时针方向; return ((p1.x-pp.x)*(p2.y-pp.y)-(p2.x-pp.x)*(p1.y - pp.y)) < -eps; } Q tra(point t,int c){ Q ans; bool flag[100]; memset(flag,false,sizeof(flag)); for(int i = 0; i < n; i++){ if(judge(t,p[i],p[i+1])){///判断能不能照到这条边 ///(实际上判断转化成了照到点); flag[i] = true; } } ///下面是处理得出的数据,保存下每个灯所能照到的最左端和最右端; if(flag[n-1]&&flag[0]){ int left = n-1; while(flag[left-1]){left--;} int right = 0; while(flag[right+1]){right++;} ans.l = left; ans.r = right + n; } else{ int left = 0,right = n-1; while(!flag[left]){left++;} while(!flag[right]){right--;} ans.l = left; ans.r = right; } ans.c = c; return ans; } bool solve() { int ans = inf; for(int i = 0; i < n; i++){ memset(f,inf,sizeof(f)); f[i] = 0; for(int j = 0; j < n; j++){ int r = i + j;///从第i个点开始往后数了j个; ///多定义这么一个层次,可以使状态的转移变得有序 for(int k = 0; k < m; k++){ if(q[k].l > r) continue;///当前点与该灯照亮的最左点之间有空隔,就不符合开始更新的条件; if(q[k].r < r) continue;///这是个剪枝,去掉也对;就是不再考虑不会成为最优解的情况; int now = min(q[k].r + 1, i + n);///根据区间右端点往后更新,但是一旦更新过了i+n就要将端点定为i+n; f[now] = min(f[now],f[r] + q[k].c); } } ans = min(ans,f[i+n]); } if(ans == inf) return false; printf("%d\n",ans); return true; } int main() { while(scanf("%d",&n) != EOF){ if(n == 0) break; for(int i = 0; i < n; i++){ p[i].read(); } p[n] = p[0]; scanf("%d",&m); point temp;int c; for(int i = 0; i < m; i++){ temp.read(); scanf("%d",&c); q[i] = tra(temp,c); } if(!solve()) printf("Impossible.\n"); } return 0; }
uva 10641 (来当雷锋的这回....)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。