海丰县建设局官方网站,广州网站营销优化qq,湖南省建设厅安许审核公布网站,桐庐县网站建设题意:按照顺时针给出操场的周边点#xff0c;然后给出周围可以建设照明灯的位置#xff0c;以及在该位置建设照明灯的代价#xff0c;照明灯照射的范围与操场的边界相切#xff0c;现在要求一个最小的花费#xff0c;要求操场的所有边都被照射到。 解题关键#xff1a;预…题意:按照顺时针给出操场的周边点然后给出周围可以建设照明灯的位置以及在该位置建设照明灯的代价照明灯照射的范围与操场的边界相切现在要求一个最小的花费要求操场的所有边都被照射到。 解题关键预处理每台灯能够覆盖到的范围然后对环进行dp即可。对环进行dp的方法是枚举起点覆盖所有点即可。 注意用叉积的方法处理灯能否照到某条边-某个点。 $dp[i][j]$表示从第$i$个点到第$j$个点之间的边都被照射到的最小代价只要有某个等得照射范围有覆盖到$i$$j$就可以向外扩展。 #includebits/stdc.h
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const double eps1e-8;
const int N105;
const int M1005;
int n,m,dp[N];
bool flag[N];
struct Point{ double x,y; Point(double x0,double y0) { this-xx; this-yy; }void read(){ scanf(%lf%lf,x,y); }
}p[N],o;struct node{ int l,r,c;
}q[M];bool judge(Point p0, Point p1, Point p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)-eps;//叉积判断是否能被照到
}node tra(Point t, int c){ node ans; ans.cc;memset(flag,0,sizeof flag); for(int i0;in;i) if(judge(t,p[i],p[i1])) flag[i]true;if (flag[0]flag[n-1]){ int ln-1,r0;while(flag[l-1]) l--; while(flag[r1]) r; ans.ll,ans.rrn;}else{ int l0,rn-1; while(!flag[l]) l;while(!flag[r]) r--;ans.ll,ans.rr; }return ans;
} bool solve(){ int ansinf; for(int i0;in;i){ fill(dp,dp2*n1,inf);dp[i]0;for(int j0;jn;j){int rij; for(int k0;km;k){if(q[k].lr) continue;int nowmin(in,q[k].r1); dp[now]min(dp[now],dp[r]q[k].c); } } ansmin(ans,dp[in]);}if(ansinf) return false;printf(%d\n,ans);return true;
} int main(){ while(~scanf(%d,n)n){for(int i0;in;i) p[i].read(); p[n]p[0];scanf(%d,m); Point tmp; int c; for(int i0;im;i){ tmp.read();scanf(%d,c); q[i]tra(tmp,c); }if (!solve()) printf(Impossible.\n); } return 0;
} 转载于:https://www.cnblogs.com/elpsycongroo/p/7808858.html
