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

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

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

angel_kitty 2017-09-02 18:01:00 浏览543

# 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

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

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

  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 }

angel_kitty
+ 关注