首页 > 代码库 > POJ 1696 Space Ant（点积的应用）

POJ 1696 Space Ant（点积的应用）

2024-07-09 05:44:36   220人阅读

Space Ant

 

大意：有一只蚂蚁，每次都只向当前方向的左边走，问蚂蚁走遍所有的点的顺序输出。开始的点是纵坐标最小的那个点，开始的方向是开始点的x轴正方向。

思路：从开始点开始，每次找剩下的点中与当前方向所形成的夹角最小的点，为下一个要走的点（好像就是犄角排序，我不是很会），夹角就是用点积除以两个向量的距离，求一下acos值。

之前一直用叉积做，做了好久样例都没过，发现用错了。。。 题目挺好的，有助于理解点积与叉积

 1 struct Point{ 2     double x, y; 3     int id; 4 } P[55], Min; 5  6 double dmult(Point p1, Point p2, Point p) 7 { 8     return (p1.x-p.x)*(p2.x-p.x)+(p1.y-p.y)*(p2.y-p.y); 9 }10 11 double Distance(Point a, Point b)12 {13     return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));14 }15 16 int T;17 int n;18 bool vis[55];19 20 void Solve()21 {22     scanf("%d", &T);23     while(T--)24     {25         memset(vis, true, sizeof(vis));26         scanf("%d", &n);27         Min = (Point){INF, INF, INF};28         for(int i = 1; i <= n; ++i)29         {30             scanf("%d%lf%lf", &P[i].id, &P[i].x, &P[i].y);31             if(P[i].y < Min.y)32             {33                 Min = P[i];34             }35         }36 37         vis[Min.id] = false;38         Point Q = (Point){0, Min.y};39         Point H = Min;40 41         printf("%d %d ", n, Min.id);42         for(int i = 2; i <= n; ++i)43         {44             double Min_a = INF;45             for(int j = 1; j <= n; ++j)46             {47                 if(vis[P[j].id] == false) continue;48                 Point t;49                 t.x = P[j].x-(H.x-Q.x);50                 t.y = P[j].y-(H.y-Q.y);51                 double x = dmult(t, H, Q);52                 double a = acos(x/Distance(Q, H)/Distance(Q, t));53                 if(a < Min_a)54                 {55                     Min_a = a;56                     Min = P[j];57                 }58             }59             vis[Min.id] = false;60             Q = H;61             H = Min;62             printf("%d", Min.id);63             printf("%s", i==n?"\n":" ");64         }65     }66 }
POJ 1696

 


联系
我们