首页 > 代码库 > 【计算几何】【状压dp】Codeforces Round #226 (Div. 2) D. Bear and Floodlight
【计算几何】【状压dp】Codeforces Round #226 (Div. 2) D. Bear and Floodlight
读懂题意发现是傻逼状压。
只要会向量旋转,以及直线求交点坐标就行了。(验证了我这俩板子都没毛病)
细节蛮多。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; const double PI=acos(-1.0); #define EPS 0.00000001 struct Point { double x,y; Point(){} Point(const double &X,const double &Y) { x=X; y=Y; } }p[23]; typedef Point Vector; Vector operator - (const Point &a,const Point &b) { return Vector(a.x-b.x,a.y-b.y); } Vector operator + (const Vector &a,const Vector &b) { return Vector(a.x+b.x,a.y+b.y); } double Cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; } Vector operator * (const double &K,const Vector &v) { return Vector(K*v.x,K*v.y); } double ang[23],f[1<<22]; int n,L,R; Vector Rotate(Vector A,double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad)); } Point GetIntersection(Point P,Vector v,Point Q,Vector w) { return P+(Cross(w,P-Q)/Cross(v,w))*v; } double calc(Point p,double rad,double x) { Vector v1=Rotate(Point(x,0)-p,rad); if(v1.y>(-EPS)) return 2147483647.0; return GetIntersection(p,v1,Point(0.0,0.0),Vector(1.0,0.0)).x; } int main() { //freopen("d.in","r",stdin); scanf("%d%d%d",&n,&L,&R); for(int i=1;i<=n;++i) { scanf("%lf%lf%lf",&p[i].x,&p[i].y,&ang[i]); ang[i]=ang[i]/180.0*PI; } for(int i=0;i<(1<<n);++i) f[i]=-2147483647.0; f[0]=L; for(int i=0;i<(1<<n);++i) for(int j=1;j<=n;++j) if(!((i>>(j-1))&1)) { f[i|(1<<(j-1))]=max(f[i|(1<<(j-1))],calc(p[j],ang[j],f[i])); if(f[i|(1<<(j-1))]-(double)R>(-EPS)) { printf("%.9lf\n",(double)(R-L)); return 0; } } printf("%.9lf\n",f[(1<<n)-1]-(double)L); return 0; }
【计算几何】【状压dp】Codeforces Round #226 (Div. 2) D. Bear and Floodlight
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。