首页 > BZOJ 4595 SHOI2015 激光发生器 射线，线段，偏转

BZOJ 4595 SHOI2015 激光发生器 射线，线段，偏转

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4595

 

题意概述：

　　给出一条射线和N条线段，射线遇到线段会发生反射，令入射角alpha，出射角beta，则beta=alpha*phi_i（即对于每条线段phi是不同的），输出至多10条遇见的线段，没有发生相交的话输出NONE。

N<=100.

 

分析：

　　实际上记得板子怎么打还是没什么问题的，问题就是我当时记不得了......

　　还有一个事情，用余弦定理求两个向量夹角的时候记得-eps控制精度！

 

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include
 8 #include<set>
 9 #include
10 #include
11 #include
12 using namespace std;
13 const int maxn=105;
14 const double eps=1e-8;
15 const double pi=acos(-1.0);
16 
17 int X,Y,dx,dy,N;
18 struct Point{
19     double x,y;
20     Point(){ }
21     Point(double xx,double yy){ x=xx,y=yy; }
22 }P[maxn]; int cnt=0;
23 typedef Point Vector;
24 struct Line{
25     Point p; Vector v;
26     Line(){    }
27     Line(Point pp,Vector vv){ p=pp,v=vv; }
28 };
29 struct data{
30     int a,b;
31     Point p1,p2;
32 }A[maxn];
33 Vector operator + (const Vector &a,const Vector &b){ return Vector(a.x+b.x,a.y+b.y); }
34 Vector operator - (const Vector &a,const Vector &b){ return Vector(a.x-b.x,a.y-b.y); }
35 Vector operator * (const Vector &a,const double &b){ return Vector(a.x*b,a.y*b); }
36 int dcmp(double x){ return fabs(x)0:(x>0?1:-1); }
37 double Dot(const Vector &a,const Vector &b){ return a.x*b.x+a.y*b.y; }
38 double Cross(const Vector &a,const Vector &b){ return a.x*b.y-a.y*b.x; }
39 double Length(const Vector &a){ return sqrt(a.x*a.x+a.y*a.y); }
40 double Angle(const Vector &a,const Vector &b){ return acos(fabs(Dot(a,b))/Length(a)/Length(b)-eps); }
41 Vector Rotate(const Vector &v,const double &rad){
42     return Vector(v.x*cos(rad)-v.y*sin(rad),v.y*cos(rad)+v.x*sin(rad));
43 }
44 Point GetLineIntersection(const Line &a,const Line &b){
45     Vector u=a.p-b.p;
46     double t=Cross(b.v,u)/Cross(a.v,b.v);
47     return a.p+a.v*t;
48 }
49 bool Onsegment(const Point &p,const Point &a,const Point &b){
50     return dcmp(Dot(a-p,b-p))<=0&&dcmp(Cross(a-p,a-p))==0;
51 }
52 
53 void data_in()
54 {
55     scanf("%d%d%d%d%d",&X,&Y,&dx,&dy,&N);
56     for(int i=1;i<=N;i++)
57         scanf("%lf%lf%lf%lf%d%d",&A[i].p1.x,&A[i].p1.y,&A[i].p2.x,&A[i].p2.y,&A[i].a,&A[i].b);
58 }
59 void work()
60 {
61     int t=1;
62     Point p=Point(X,Y),pp;
63     Vector v=Vector(dx,dy),vv;
64     while(t<=10){
65         double md=1e9,dis; int id=0;
66         for(int i=1;i<=N;i++){
67             if(dcmp(Cross(A[i].p1-A[i].p2,v))==0) continue;
68             pp=GetLineIntersection(Line(A[i].p1,A[i].p2-A[i].p1),Line(p,v));
69             if(Onsegment(pp,A[i].p1,A[i].p2)&&dcmp(Dot(v,pp-p))>0){
70                 dis=Length(p-pp);
71                 if(disi;
72             }
73         }
74         if(!id) break;
75         p=GetLineIntersection(Line(A[id].p1,A[id].p2-A[id].p1),Line(p,v));
76         if(dcmp(Dot(A[id].p1-A[id].p2,v))==0) v=v*-1;
77         else{
78             if(dcmp(Dot(A[id].p1-A[id].p2,v))>0) vv=A[id].p1-A[id].p2;
79             else vv=A[id].p2-A[id].p1;
80             double alp=pi/2-Angle(vv,v);
81             if(dcmp(Cross(vv,v))>0) v=Rotate(vv,alp*A[id].a/A[id].b-pi/2);
82             else v=Rotate(vv,pi/2-alp*A[id].a/A[id].b);
83         }
84         printf("%d ",id);
85         t++;
86     }
87     if(t==1) printf("NONE
");
88 }
89 int main()
90 {
91     data_in();
92     work();
93     return 0;
94 }
View Code

 

转载于:https://www.cnblogs.com/KKKorange/p/8646447.html

更多相关：

  • 基于SfM计算相机姿态

    具体过程为： ① 通过相机标定方法，预先计算相机的内参矩阵； ② 相邻帧特征点匹配，并结合内参矩阵计算本征矩阵； ③ 本征矩阵分解获得相机的外参矩阵[R | T]，最终的相机移动距离等于矩阵T的Frobenius范数。 #include #include

  • 剑指offer：面试题34. 二叉树中和为某一值的路径

    题目：二叉树中和为某一值的路径 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例: 给定如下二叉树，以及目标和 sum = 22，               5              /             4   8    ...

  • vector容器 begin()与end()函数、front()与back()的用法

    begin函数： 函数原型: iterator begin(); const_iterator begin(); 功能： 返回一个当前vector容器中起始元素的迭代器。 end函数： 函数原型： iterator end(); const_iterator end(); 功能： 返回一个当前vector容器中末尾元素的迭代器。...

  • C++ STL: 容器vector源码分析

    文章目录前言vector的核心接口vector push_back实现vector 的 Allocatorvector 的 push_back总结...

  • leetcode-102 二叉树的层次遍历

    给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树: [3,9,20,null,null,15,7] 3 / 9 20 / 15 7 返回其层次遍历结果： [ [3], [9,20], [15,7] ] 方法一（非递归） 二叉树的层次遍历即二叉树的广度遍历，可以使...

  • C++ mutable

    mutable的中文意思是“可变的，易变的”，跟constant（既C++中的const）是反义词。 　　在C++中，mutable也是为了突破const的限制而设置的。被mutable修饰的变量，将永远处于可变的状态，即使在一个const函数中。 　　我们知道，如果类的成员函数不会改变对象的状态，那么这个成员函数一般会声明成cons...

  • const int * 、int * const、int const* 、const int a(){ } 和int a()const { }的区别和联系

    前言：很多人都把const int * 、int * const、int const* 的区别和联系搞混，我自己在学习C++的过程中，也经常性          弄不 清楚，今天特意总结一下，作为学习笔记记录下来。 一，const修饰符用于指针         将const用于指针有些很微妙的地方，有两种不同的方式将const关键...

  • Node.js实现服务器端生成Excel文件（xls格式、xlsx格式文件）并弹出下载文件

      注意，前情提示： 本代码基于《Node.js（nodejs）对本地JSON文件进行增、删、改、查操作（轻车熟路）》 传送门Node.js（nodejs）对本地JSON文件进行增、删、改、查操作（轻车熟路）_你挚爱的强哥❤给你发来1条消息❤-CSDN博客   在/api/demo/文件夹下面创建exportAndDownl...

  • Node.js开发WEB项目后端接口API，基于mysql5.7数据库（小试牛刀）

    项目结构 main.js（入口文件，开启9999端口监听，实现RESTful风格接口访问） const express = require("express"); const app = express(); const port = 9999;//设置端口号，如果端口号被占用需要自己修改，否则无法跑起来(建议不要用80和80...

  • ES6 你可能不知道的事 – 基础篇

    ES6 你可能不知道的事 – 基础篇 转载 作者：淘宝前端团队（FED）- 化辰 链接：taobaofed.org/blog/2016/07/22/es6-basics/   序   ES6，或许应该叫 ES2015（2015 年 6 月正式发布），对于大多数前端同学都不陌生。   首先这篇文章不是工具书，不会去过多谈概念，而是...

  • 【全网唯一】全网唯一能够跑通的，跑不通你来找我~用node.js完成微信支付下单功能，且只需要一个文件wxpay.js就解决业务

        先吐为敬！   最近心血来潮研究nodejs如何完成微信支付功能，结果网上一搜索，一大堆“代码拷贝党”、“留一手”、“缺斤少两”、“不说人话”、“自己都没跑通还出来发blog”、“各种缺少依赖包”、“各种注释都没有”、“自己都不知道在写什么”的程序大神纷纷为了增加自己博客一个帖子的名额而发布了各种千奇百�...

  • ceph bluestore源码分析：C++ 获取线程id

    阅读ceph源码过程中需要明确当前操作是由哪个线程发出，此时需要根据线程id来确认线程名称 C++获取线程id是通过系统调用来直接获取 函数描述 头文件: 函数名称:syscall(SYS_gettid) 该函数直接返回了一个pid_t int类型的数字，即为当前线程id 此外函数pthread_s...

  • 分库分表之后，主键的处理方法

    面试题 分库分表之后，id 主键如何处理？ 面试官心理分析 其实这是分库分表之后你必然要面对的一个问题，就是 id 咋生成？因为要是分成多个表之后，每个表都是从 1 开始累加，那肯定不对啊，需要一个全局唯一的 id 来支持。所以这都是你实际生产环境中必须考虑的问题。 面试题剖析 基于数据库的实现方案 数据库自增 id 这个就是说你的...

  • ORM操作models一对多、多对多关系

    ORM操作    单表、一对多表操作 1 from django.db import models 2 3 4 class UserGroup(models.Model): 5 title = models.CharField(max_length=32) 6 7 8 class UserInfo(m...

  • mysql的小练习

    建立如下表： 建表语句： class表创建语句 create table class(cid int not null auto_increment primary key, caption varchar(32) not null)engine=innodb default charset=utf8;student表创建语句 c...

©2024 11GX.COM