【计算几何】【状压dp】Codeforces Round #226 (Div. 2) D. Bear and Floodlight
2024-10-21 23:09:09
读懂题意发现是傻逼状压。
只要会向量旋转,以及直线求交点坐标就行了。(验证了我这俩板子都没毛病)
细节蛮多。
#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;
}
最新文章
- jqGrid jqGrid分页参数+条件查询
- 第18章 集合框架(2)-Set接口
- iOS UITableView 分割线从零开始
- 简述memcached中的一致哈希
- Unity Sprite转Prefab
- [JS] JavaScript框架(1) jQuery
- Sharepoint学习笔记—习题系列--70-573习题解析 -(Q32-Q34)
- adbd cannot run as root in production builds
- _doPostBack用法总结
- poj 3253 Fence Repair(优先队列+哈夫曼树)
- JVM性能调优监控工具jps、jstack、jmap、jhat、jstat使用详解
- cpp(第八章)
- hadoop学习第一天-hadoop初步环境搭建&;伪分布式计算配置(详细)
- 如何在java注解中加入原生html标签内容
- 金融量化分析【day112】:均值回归策略
- win10 win7 环境下 oracle 11g和Plsql的安装、卸载遇到的问题。
- C#基础知识之读取xlsx文件Excel2007
- golang fmt格式“占位符”
- OWASP TOP 10 2017中文译文
- Json.NET Updates: Merge, Dependency Injection, F# and JSONPath Support