EOJ3059：极坐标排序算法解析

本题包含7个讨论案例，要求在2秒的时间限制和256MB的内存限制下完成。题目描述了如何在一个平面上使用两种不同的坐标系——直角坐标系和极坐标系来定位点的位置。

当极坐标系的极点O与直角坐标系的原点O重合，且极轴OX与直角坐标系的X轴正方向一致，同时两者的单位长度相同，这时可以通过特定公式将直角坐标转换为极坐标。

例如，直角坐标(1, 1)对应的极坐标为(1.4142, π/4)，而直角坐标(-1, 1)对应的极坐标则是(1.4142, 3π/4)。

题目要求接收一系列直角坐标点，计算并输出这些点的极坐标形式，首先按照极角θ升序排列，若极角相同，则按极径ρ降序排列。极角范围限定在0至2π之间，极径ρ非负。

输入格式

第一行输入整数T (1≤T≤10)，表示测试用例的数量。每个测试用例的第一行输入正整数N (1≤N≤1000)，表示点的数量；随后N行，每行包含两个浮点数x, y，表示点的直角坐标。

输出格式

对于每个测试用例，首先输出一行问题编号（从0开始，格式如：case #0:）。接着输出N行，每行输出一个点的极坐标(ρ, θ)，其中ρ保留四位小数，θ以弧度表示。

示例

输入示例：

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)

以下是解决该问题的一个C++代码示例：

#include 
#include 
#define pi 3.1415926
using namespace std;

struct Point {
    double x, y;
    double radius, angle;
};

bool compare(const Point& a, const Point& b) {
    if (fabs(a.angle - b.angle) > 1e-9) return a.angle     return a.radius > b.radius;
}

int main() {
    int T, N;
    cin >> T;
    for (int t = 0; t         cin >> N;
        Point points[N];
        for (int i = 0; i             cin >> points[i].x >> points[i].y;
            points[i].radius = sqrt(points[i].x * points[i].x + points[i].y * points[i].y);
            points[i].angle = atan2(points[i].y, points[i].x);
            if (points[i].angle <0) points[i].angle += 2 * pi;
        }
        sort(points, points + N, compare);
        cout <<"case #" <        for (int i = 0; i             printf("(%.4lf,%.4lf)\n", points[i].radius, points[i].angle);
        }
    }
    return 0;
}