1 /*
2 近兩個小時
3 錯誤有三：1 dis函數a.y - b.y 又一次寫成了 a.y - a.y;
4 2 角度旋轉時沒有考慮方向性，是向左轉，還是向右轉。沒有考慮清楚
5 3 第11次如果還碰到就輸出
，否則輸出inf
6 */
7 #include<iostream>
8 #include<algorithm>
9 #include<cmath>
10 using namespace std;
11
12 const int maxn = 30;
13 int x[maxn], y[maxn], r[maxn];
14
15 struct Ray{
16 double x, y, dx, dy;
17 };
18 Ray ray;
19 int n;
20
21 double dis(Ray a, Ray b){
22 return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
23 }
24
25 double get_angle(double x0, double y0, double x1, double y1){
26 return atan2(x0*y1 - x1*y0, x0*x1 + y0*y1) ;
27 }
28
29 bool get(Ray ray, int id, Ray & next){
30 double a = ray.dx * ray.dx + ray.dy * ray.dy;
31 double b = 2 * ray.dx * (ray.x - x[id]) + 2 * ray.dy * (ray.y - y[id]);
32 double c = (ray.x - x[id])*(ray.x - x[id]) + (ray.y - y[id])*(ray.y - y[id]) - 1.0 * r[id] * r[id];
33 double delta = b*b - 4*a*c;
34 if(delta < 0)return false;
35 double p = (-b - sqrt(delta) ) / (2 * a);
36 if(p <= 1e-8)return false;
37 next.x = ray.dx * p + ray.x;
38 next.y = ray.dy * p + ray.y;
39 double theta = get_angle(ray.dx, ray.dy, next.x - x[id], next.y - y[id] )
40 - get_angle(next.x - x[id], next.y - y[id], -ray.dx, -ray.dy);
41 next.dx = ray.dx * cos(theta) - ray.dy * sin(theta);
42 next.dy = ray.dx * sin(theta) + ray.dy * cos(theta);
43 return true;
44 }
45
46 void solve(){
47 int i, j;
48 for(i = 0; i < 11; i++){
49 Ray best, next_ray;
50 bool first = true;
51 int id;
52 for(j = 0; j < n; j++)
53 if( get(ray, j, next_ray) ){
54 if(first || dis(best, ray) > dis(next_ray, ray) ){
55 first = false;
56 best = next_ray;
57 id = j;
58 }
59 }
60 if(first)break;
61 if(i < 10)printf("%d ",id+1);
62 ray = best;
63 }
64 if(i==11){
65 printf("\n");
66 }else
67 printf("inf\n");
68 }
69
70 int main()
71 {
72 int cas = 1;
73 while(scanf("%d",&n) && n){
74 for(int i = 0; i < n; i++)
75 scanf("%d %d %d",&x[i], &y[i], &r[i]);
76 scanf("%lf %lf %lf %lf",&ray.x, &ray.y, &ray.dx, &ray.dy);
77 printf("Scene %d\n",cas++);
78 solve();
79 printf("\n");
80 }
81 }
posted on 2009-10-25 00:06
wangzhihao 閱讀(120)
評論(0) 編輯 收藏 引用 所屬分類:
geometry