读懂题意发现是傻逼状压。

只要会向量旋转,以及直线求交点坐标就行了。(验证了我这俩板子都没毛病)

细节蛮多。

#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;
}

最新文章

  1. jqGrid jqGrid分页参数+条件查询
  2. 第18章 集合框架(2)-Set接口
  3. iOS UITableView 分割线从零开始
  4. 简述memcached中的一致哈希
  5. Unity Sprite转Prefab
  6. [JS] JavaScript框架(1) jQuery
  7. Sharepoint学习笔记—习题系列--70-573习题解析 -(Q32-Q34)
  8. adbd cannot run as root in production builds
  9. _doPostBack用法总结
  10. poj 3253 Fence Repair(优先队列+哈夫曼树)
  11. JVM性能调优监控工具jps、jstack、jmap、jhat、jstat使用详解
  12. cpp(第八章)
  13. hadoop学习第一天-hadoop初步环境搭建&amp;伪分布式计算配置(详细)
  14. 如何在java注解中加入原生html标签内容
  15. 金融量化分析【day112】:均值回归策略
  16. win10 win7 环境下 oracle 11g和Plsql的安装、卸载遇到的问题。
  17. C#基础知识之读取xlsx文件Excel2007
  18. golang fmt格式“占位符”
  19. OWASP TOP 10 2017中文译文
  20. Json.NET Updates: Merge, Dependency Injection, F# and JSONPath Support

热门文章

  1. POJ1459:Power Network(多源点多汇点的最大流)
  2. LA2995 Image is everything
  3. eclipse tomcat 插件
  4. Java并发(10)- 简单聊聊JDK中的七大阻塞队列
  5. [转]华 使用npm安装一些包失败了的看过来(npm国内镜像介绍)
  6. Mac git
  7. mhn 实际部署记录
  8. algorithm ch6 heapsort
  9. ZOJ 3598 Spherical Triangle球面几何公式应用
  10. HashMap扩容函数解读