3059. 极坐标排序

单点时限: 2.0 sec

内存限制: 256 MB

在平面上，确定一个点的位置通常有下面两种表示方法：

当极坐标系中的极点 O 与直角坐标系中的原点 O 重合，极轴 OX 与直角坐标系中的 X 轴的正半轴重合，并且两种坐标系的单位长度相同，那么平面内任意一点 P 的直角坐标与极坐标可以互相转换。

例如：

点 p 直角坐标为：，(1，1)，则对应的极坐标为：(1.4142,π4)。

点 p 直角坐标为：，(?1，1)，则对应的极坐标为：(1.4142,3π4)。

点 p 直角坐标为：，(?1，?1)，则对应的极坐标为：(1.4142,5π4)。

点 p 直角坐标为：，(1，?1)，则对应的极坐标为：(1.4142,7π4)。

点 p 直角坐标为：，(0，1)，则对应的极坐标为：(1,π2)。

点 p 直角坐标为：，(1，0)，则对应的极坐标为：(1,0)。

给出 N 个点的直角坐标 (x,y)，请计算出这些点对应的极坐标，将这 N 个点按照极角 θ 从小到大排序，如果两个点的极角相同，则将它们按照极径 ρ 由大到小排序。

注意：ρ≥0，极角 0≤θ<2π

输入格式

第 1 行：整数 T (1≤T≤10) 为问题数。

对于每个问题，按如下格式输入：

第 1 行：输入一个正整数 N(1≤N≤1000)，表示点的个数；

接下来 N 行，每行输入两个浮点数 x,y，表示点的直角坐标，两个数之间由一个空格分隔。

输出格式

对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等）。

接下来 N行输出排序后的点的极坐标（ρ,θ），每行输出一个点的极坐标，小数点后保留 4 位，极角采用弧度表示。

样例

3
5
1.0 1.0
2.0 2.0
-1.0 1.0
0 1.0
1.0 0
1
0 -1.0
6
1.0 1.0
0 1.0
1.0 0
-1.0 1.0
-1.0 -1.0
1.0 -1.0

case #0:
(1.0000,0.0000)
(2.8284,0.7854)
(1.4142,0.7854)
(1.0000,1.5708)
(1.4142,2.3562)
case #1:
(1.0000,4.7124)
case #2:
(1.0000,0.0000)
(1.4142,0.7854)
(1.0000,1.5708)
(1.4142,2.3562)
(1.4142,3.9270)
(1.4142,5.4978)

#include 
#include 
#include <string.h>
#define pi 3.1415926
using namespace std;
struct point
{
    double x, y;
    double p, r;
} zuo[1001];
int cmp(const void *a, const void *b)
{
    struct point *aa = (point *)a;
    struct point *bb = (point *)b;
    if (fabs(aa->r - bb->r) > 1e-9)
    {
        if (aa->r - bb->r > 0)
            return 1;
        else
            return -1;
    }
    else
        return bb->p - aa->p;
}

int main()
{
    int t;
    cin >> t;
    int n, ret = 0;
    while (t--)
    {

        cin >> n;
        int i;
        for (i = 0; i < n; i++)
        {
            cin >> zuo[i].x >> zuo[i].y;
            zuo[i].p = sqrt(zuo[i].x * zuo[i].x + zuo[i].y * zuo[i].y);

            double t = atan2(zuo[i].y, zuo[i].x);
            zuo[i].r = t;
            if (t < 0)
                zuo[i].r += 2 * pi;
        }
        qsort(zuo, n, sizeof(zuo[0]), cmp);
        cout << "case #" << ret++ << ":" << endl;
        for (i = 0; i < n; i++)
        {
            printf("(%.4lf,%.4lf)\n", zuo[i].p, zuo[i].r);
        }
    }
}
/*一些要说的话,写cmp    拿double比较大小排序时一定要注意:
          1.相等用fbs(x-y)<1e-10表示
         2. 有int 返回值时,不能直接返回double相减的值,应该比较两数大小后,用1和-1作为返回值,否则若存在小数,会返回0值令结果错误
         3.其他,atan2函数表示区间为(-pi,pi)若要用来转换(0,2pi),可以直接在负结果后+2pi
         但是务必注意atan2(double y,double x)第一个参数为纵坐标(被坑惨了,/(ㄒoㄒ)/~~)*/