2017 Multi-University Training Contest - Team 9 1004&&HDU 6164 Dying Light【数学+模拟】

Dying Light

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 513    Accepted Submission(s): 122

Problem Description

LsF is visiting a local amusement park with his friends, and a mirror room successfully attracts his attention. Inside the mirror room, there are n plane mirrors standing vertically on the ground. They are placed end-to-end and face-to-face so that if you overlook the room, you can find a convex hull and the all the reflector surfaces are inside the pattern. The height of the mirror is not important in this problem. Due to imperfect manufacturing techniques, mirrors can't reflect light without lose of energy. Each mirror has a reflection efficiency k, which means if the incident light's intensity is I, the reflected light's intensity will be reduced to kI. The only exception could happen when the light precisely goes to the two mirrors' junction. In that case, the light will be completely absorbed instantly. Note the laws of reflection of light applies in all other situations, that the angle of incidence equals the angle of reflection. Now LsF stands inside the mirror hall, and shoots a laser beam paralleled to the ground using his laser pointer. Unfortunately, his laser pointer can only shot laser beams with intensity of 1. What's worse, a laser beam is considered disappeared if its intensity is below 10−4. There's not much magnitude distance between the two numbers. LsF wants to know how many touches can his laser beam make with mirrors before it disappears.

Input

The first line contains an integer n(3≤n≤1000), indicating the number of mirrors; Then n lines follow. The ith line contains three real numbers xi,yi,ki(−109≤xi,yi≤109;0≤ki≤0.9), which means the ith mirror's one end is at position (xi,yi) and another end is at (xi+1mod n,yi+1mod n), and its reflectivity is ki. Next there are two real numbers Vx,Vy(-109≤Vx,Vy≤109), indicating the initial direction vector of the laser beam. LsF is standing at the origin (0, 0).

Output

Output an integer in one line, the number of touches the laser beam could make before it disappears.

Sample Input

4
1 2 0.5
-1 0 0.5
1 -2 0.5
3 0 0.5
0 1
4
1 1 0.5
-1 1 0.5
-1 -1 0.5
1 -1 0.5
1 1

Sample Output

14
1

Source

2017 Multi-University Training Contest - Team 9

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6164

分析:由于LsF一开始不再镜子上,按题面模拟即可。 由于反射率<=0.9 0.9^100<1e-4,所以反射次数不会超过100次。 每次暴力判断和哪个镜子相交,以及有没有在镜子焦点上。

下面给出AC代码:

  1 #include <cstring>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <iostream>
  5 
  6 #define MAXN 5000
  7 #define eps 1e-9
  8 
  9 struct point
 10 {
 11     double x,y;
 12     point(double a = 0,double b = 0)
 13     {
 14         x = a; y = b;
 15     }
 16     friend point operator + (point a,point b)
 17     {
 18         return point(a.x+b.x,a.y+b.y);
 19     }
 20     friend point operator - (point a,point b)
 21     {
 22         return point(a.x-b.x,a.y-b.y);
 23     }
 24     friend double operator ^ (point a,point b)
 25     {
 26         return a.x*b.y-a.y*b.x;
 27     }
 28     friend double operator * (point a,point b)
 29     {
 30         return a.x*b.x+a.y*b.y;
 31     }
 32     friend point operator * (point a,double b)
 33     {
 34         return point(a.x*b,a.y*b);
 35     }
 36     friend point operator * (double a,point b)
 37     {
 38         return point(a*b.x,a*b.y);
 39     }
 40 
 41 };
 42 
 43 struct line
 44 {
 45     point s,e;
 46     line(point a = point(0,0),point b = point(0,0))
 47     {
 48         s = a; e = b;
 49     }
 50 };
 51 
 52 point p[MAXN+5];
 53 double c[MAXN+5];
 54 int n;
 55 point s[2];
 56 
 57 int sgn(double x)
 58 {
 59     if (x>eps) return 1;
 60     if (x<-eps) return -1;
 61     return 0;
 62 }
 63 
 64 point Get_Intersect(line a,line b)
 65 {
 66     double u=(a.e-a.s)^(b.s-a.s);
 67     double v=(a.s-a.e)^(b.e-a.e);
 68     point p;
 69     p.x=(b.s.x*v+b.e.x*u)/(v+u);
 70     p.y=(b.s.y*v+b.e.y*u)/(v+u);
 71     return p;
 72 }
 73 
 74 int main()
 75 {
 76 //    freopen("input.txt","r",stdin);
 77     while(scanf("%d",&n)!=EOF)
 78     {for (int i=0;i<n;i++) scanf("%lf%lf%lf",&p[i].x,&p[i].y,&c[i]);
 79     p[n] = p[0];
 80     s[0] = point(0,0);
 81     scanf("%lf%lf",&s[1].x,&s[1].y);
 82 
 83     double now = 1.0;
 84     int ans = 0;
 85     bool flag = 1;
 86     point temp;
 87     point temp2;
 88     line l1,l2,l3,l4;
 89     while (now > 1e-4)
 90     {
 91         ans++;
 92         for (int i=0;i<n;i++)
 93         {
 94             if (!sgn((p[i]-s[0])^s[1]))
 95             {
 96                 now = 0;
 97                 flag = 0;
 98                 break;
 99             }
100         }
101         if (!flag) break;
102         for (int i=0;i<n;i++)
103         {
104             if (sgn((p[i]-s[0])^s[1]) > 0 && sgn(s[1]^(p[i+1]-s[0]))>0)
105             {
106                 l1 = line(p[i+1],p[i]);
107                 l2 = line(s[0],s[1]+s[0]);
108                 temp = Get_Intersect(l1,l2);
109 
110                 l3 = line(temp,point(p[i+1].y-p[i].y,p[i].x-p[i+1].x)+temp);
111                 l4 = line(s[0],point(p[i].x-p[i+1].x,p[i].y-p[i+1].y)+s[0]);
112 
113                 temp2 = Get_Intersect(l3,l4);
114                 temp2 = 2*temp2-s[0];
115                 s[0] = temp;
116                 s[1] = temp2-s[0];
117                 now *= c[i];
118                 break;
119             }
120         }
121     }
122     printf("%d\n",ans);
123     }
124     return 0;
125 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 1010 Tempter of the Bone【DFS经典题+奇偶剪枝详解】

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 6553...

34640
来自专栏ml

hduoj----(1033)Edge

Edge                         Time Limit: 2000/1000 MS (Java/Others)    Memory Li...

31560
来自专栏xingoo, 一个梦想做发明家的程序员

HDOJ 1006

Tick and Tick Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/327...

21790
来自专栏ml

hduoj----1142A Walk Through the Forest(记忆化搜索+最短路)

A Walk Through the Forest Time Limit: 2000/1000 MS (Java/Others)    Memory Limit...

34860
来自专栏数据结构与算法

HDU2837 Calculation(扩展欧拉定理)

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe...

10020
来自专栏ml

HDUOJ---------(1045)Fire Net

Fire Net Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (...

34850
来自专栏机器学习与自然语言处理

POJ2488-A Knight's Journey(DFS+回溯)

题目链接:http://poj.org/problem?id=2488 A Knight's Journey Time Limit: 1000MS ...

25790
来自专栏calmound

POJ 1365 Prime Land

                  Prime Land Time Limit: 1000MS Memory Limit: 10000K Tot...

28640
来自专栏ml

hdu-------1081To The Max

To The Max Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K...

30360
来自专栏ml

HDUOJ----Super Jumping! Jumping! Jumping!

Super Jumping! Jumping! Jumping! Time Limit : 2000/1000ms (Java/Other)   Memory ...

28660

扫码关注云+社区

领取腾讯云代金券