随笔-21  评论-10  文章-21  trackbacks-0
 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*- 4*a*c;
34     if(delta < 0)return false;
35     double p = (-- 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            ifget(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 阅读(111) 评论(0)  编辑 收藏 引用 所属分类: geometry

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理