HDU 1785 You Are All Excellent：利用 atan2 函數按向量極角排序

問題背景

HDU 1785「You Are All Excellent」是一道經典的計算幾何入門題。題目描述了一個選拔隊員的場景：原本依據隊員到原點的歐幾里得距離排名，後改為依據隊員位置向量與 X 軸正方向的夾角（極角）從小到大排序。所有隊員的 y 座標均為正數，且座標保留一位小數。輸入包含多組測試數據，每組先給出人數 n (n ≤ 100)，再給出 2n 個浮點數表示座標；n 為負數時結束。輸出要求按新規則排序後的座標，每組佔一行，座標間以空格分隔。

核心思路：atan2 函數求極角

關鍵在於如何正確計算向量與 X 軸的夾角。C/C++ 標準庫 <cmath> (或 math.h) 提供的 atan2(y, x) 函數恰好能滿足需求：它返回點 (x, y) 相對於原點的極角，範圍為 [-π, π]。由於題目保證所有 y > 0，極角將落在 (0, π) 區間，直接按此值升序排序即可得到題目要求的排名。注意 atan2 的參數順序是 先 y 後 x，這是常見易錯點。

算法步驟

1. 讀入 n，若 n < 0 則結束。
2. 為每位隊員讀取座標 (x, y)，計算 angle = atan2(y, x) 並存入結構體。
3. 使用 std::sort 按 angle 升序排序。
4. 按格式輸出排序後的座標，保留一位小數。

參考代碼 (C++)

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

struct Player {
    double x, y;
    double angle;
} players[105];

bool cmp(const Player &a, const Player &b) {
    return a.angle < b.angle;
}

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n >= 0) {
        for (int i = 0; i < n; ++i) {
            scanf("%lf%lf", &players[i].x, &players[i].y);
            players[i].angle = atan2(players[i].y, players[i].x);
        }
        sort(players, players + n, cmp);
        printf("%.1lf %.1lf", players[0].x, players[0].y);
        for (int i = 1; i < n; ++i) {
            printf(" %.1lf %.1lf", players[i].x, players[i].y);
        }
        puts("");
    }
    return 0;
}

複雜度分析

每組測試數據：計算極角 O(n)，排序 O(n log n)，n ≤ 100，時間與記憶體均極易滿足限制。

常見陷阱提醒

• atan2 參數順序為 (y, x)，切勿寫反。
• 輸入以負數 n 結束，而非 EOF，需注意循環條件。
• 題目保證排名唯一，無需處理極角相等的情況。
• 輸出格式：每組一行，座標間單個空格，行末無多餘空格。