Space Ant POJ - 1696
题目链接: https://vjudge.net/problem/POJ-1696
题意: 给你很多点的坐标, 一只蚂蚁要最多可以经过多少点, 且每经过一个点的路线不能和之前经过的路线重复相交, 该蚂蚁只能直线走或者向左边走
思路: 找到纵坐标最小 (纵坐标相等横坐标满足最小) 的点作为起始点, 对剩下的点相当于极角排序, 利用叉积, 求出最外面的凸包相对于该起始点的下一点, 然后将改点作为剩余点的起始点, 再对剩下的点进行极角排序, 得出最外凸包过程中的下一点, 重复操作, 故肯定能把所有的点走完
- //
- // Created by HJYL on 2020/1/17.
- //
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<cmath>
- #include<algorithm>
- using namespace std;
- const double eps=1e8;
- int dcmp(double x)
- {
- if(fabs(x)<eps)
- return 0;
- return x<0?-1:1;
- }
- struct Point{
- double x,y;
- int id;
- Point(){}
- Point(int id,double x,double y):id(id),x(x),y(y){}
- }initial;// 以当前点来求最外凸包
- typedef Point Vector;
- Vector operator-(Point A,Point B)
- {
- return Vector(-1,A.x-B.x,A.y-B.y);
- }
- // 叉积
- double Cross(Vector A,Vector B)
- {
- return A.x*B.y-A.y*B.x;
- }
- double Len(Point A,Point B)
- {
- return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
- }
- // 极角排序
- bool cmp(const Point& A,const Point& B)
- {
- double t=Cross(A-initial,B-initial);
- if(t>0)// 叉积大于 0,B 在 A 的左边, A 在外凸包上
- return true;
- else if(t<0)
- return false;
- else
- return Len(A,initial)<Len(B,initial);// 极角相同采用最近的点
- }
- const int maxn=100;
- int main()
- {
- Point p[maxn];
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int n;
- scanf("%d",&n);
- initial=Point(0,1e10,1e10);// 初始化一开始的点
- for(int i=0;i<n;i++)
- {
- scanf("%d%lf%lf",&p[i].id,&p[i].x,&p[i].y);
- if(initial.y>p[i].y||(initial.y==p[i].y&&initial.x>p[i].x))// 找出最下面且最左边的点
- initial=Point(p[i].id,p[i].x,p[i].y);// 更新原始点
- }
- swap(p[0],p[initial.id-1]);// 将点集的第一点为原始要操作的点
- int serial[maxn];
- int pos=0;
- serial[pos++]=initial.id;// 输出的序号数组, 第一个就是原始操作的点
- for(int i=1;i<n;i++)
- {
- sort(p+i,p+n,cmp);// 对剩下的点进行极角排序
- initial=p[i];// 更新原始点
- serial[pos++]=p[i].id;
- }
- printf("%d",n);
- for(int i=0;i<pos;i++)
- printf("%d",serial[i]);
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3385122.html