排序中文POJ 1696/hrbustoj 1318 几何 蛋疼的蚂蚁

本文纯属个人见解，是对前面学习的总结，如有描述不正确的地方还请高手指正~

    链接：POJ(英文)：http://poj.org/problem?id=1696

               hrbustoj(中文)：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1318

    分析：逆时针极角排序(除了第一个点对y排序)

    

    每日一道理
如果只看到太阳的黑点，那你的生活将缺少温暖；如果你只看到月亮的阴影，那么你的生命历程将难以找到光明；如果你总是发现朋友的缺点，你么你的人生旅程将难以找到知音；同样，如果你总希望自己完美无缺，假设你的这一愿望真的能如愿以偿，那么你最大的缺点就是没有缺点。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>

using namespace std;
const int maxn=100000;

struct point{
    int u;
    int x, y;
    void read(){
        cin>>u>>x>>y;
    }
}f[105],cur;

bool cmp_y(point a,point b){///对y排序
    return a.y<b.y;
}

double cross(point p0,point p1,point p2){///两向量叉积
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

double dis(point a,point b){///两点距离
    return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}

bool cmp(point a,point b){///极角排序
    double ret = cross(cur,a,b);
    if(ret>0) return true;
    if(ret<0) return false;
    double x = dis(cur,a);
    double y = dis(cur,b);
    if(x<y) return true;///a靠得近
    return false;
}

int main(){
    int T; cin>>T;
    while(T--){
        int n; cin>>n;
        for(int i=0;i<n;++i)
            f[i].read();
        for(int i=0;i<n;++i){
            if(!i)sort(f+i,f+n,cmp_y);
            else  sort(f+i,f+n,cmp);
            cur = f[i];
            if(!i)cout<<n;
            cout<<' '<<f[i].u;
        }
        cout<<endl;
    }
    return 0;
}

文章结束给大家分享下程序员的一些笑话语录： 腾讯总舵主马化腾，有人曾经戏称如果在Z国选举总统，马化腾一定当选，因为只要QQ来一个弹窗”投马总，送Q币”即可。