poj 1696 极角排序（解题报告）

浅浅的花香味﹌ 2021-11-01 13:16 275阅读 0赞

#include<iostream>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    double eps=1e-8;
    int sgn(double x)
    {
        if(fabs(x)<=eps)return 0;
        if(x<0)return -1;
        return 1;
    }
    struct Point
    {
        double x,y;
        int index;
        Point (){}
        Point(double _x,double _y)
        {
            x=_x;
            y=_y;
        }
        Point operator -(const Point &b)const
        {
            return Point(x-b.x,y-b.y);
        }
        double operator *(const Point &b)const
        {
            return x*b.x+y*b.y;
        }
        double operator ^(const Point &b)const
        {
            return x*b.y-y*b.x;
        }
    };
    
    double dist(Point a,Point b)
    {
        return sqrt((a-b)*(a-b));
    }
    int pos;
    Point p[100];
    bool cmp(Point a,Point b)
    {
        double tmp=sgn((a-p[pos])^(b-p[pos]));
        if(tmp==0)return dist(a,p[pos])<dist(b,p[pos]);
        if(tmp<0)return false;
        return true;
    
    }
    
    int main ()
    {
        int T;
        cin>>T;
        int n;
        while(T--)
        {
            cin>>n;
            for(int i=0;i<n;i++)
            {
                cin>>p[i].index>>p[i].x>>p[i].y;
                if(p[i].y<p[0].y||(p[i].y==p[0].y&&p[i].x<p[0].x))
                    swap(p[0],p[i]);
            }
            pos=0;
            for(int i=1;i<n;i++)
            {
                sort(p+i,p+n,cmp);//这里是i,排序i后的点
                pos++;
            }
            cout<<n;
            for(int i=0;i<n;i++)
                cout<<' '<<p[i].index;
            cout<<endl;
        }
    
        return 0;
    
    }

题意：有一个蚂蚁。在一个平面上吃植物，这个蚂蚁只能往左走，求蚂蚁最多能吃到多少植物，并将路线输出

转化：最多能将所有的植物都吃完。只要绕最外边一圈逆时针往前走，一直走到最里边的 一个植物即可

通过极角排序，先按照左下角植物排序，绕逆时针依次为极点进行排序，排到最后一个点输出即可

转载于:https://www.cnblogs.com/zwx7616/p/11219392.html