HDU 1209 Clock：時鐘夾角中位數 (排序)

問題描述

給定 5 個不同時刻（格式 hh:mm，24 小時制），計算時針與分針夾角（取較小角，0°~180°）。按夾角升序排序，夾角相同時刻早者在前。輸出第 3 個（中位數）時刻。

夾角計算公式

時針速度：0.5°/分（360°/12h = 30°/h = 0.5°/分）。分針速度：6°/分（360°/60分）。

時刻 H:M（H 取 12 制）：

hour_angle = (H % 12) * 30 + M * 0.5
minute_angle = M * 6
diff = abs(hour_angle - minute_angle)
angle = min(diff, 360 - diff)

算法流程

1. 解析 5 個時刻，計算夾角存入結構體 (h, m, angle)。
2. 排序：先按 angle 升序，再按 h*60+m 升序（時間早者在前）。
3. 輸出排序後第 3 個元素（下標 2），格式 %02d:%02d。

參考代碼 (Java)

import java.util.*;
public class ClockMedian {
    static class Time implements Comparable {
        int h, m; double angle;
        Time(int h, int m) {
            this.h = h; this.m = m;
            double ha = (h % 12) * 30.0 + m * 0.5;
            double ma = m * 6.0;
            double d = Math.abs(ha - ma);
            angle = Math.min(d, 360 - d);
        }
        public int compareTo(Time o) {
            if (Math.abs(angle - o.angle) > 1e-9)
                return Double.compare(angle, o.angle);
            return (h * 60 + m) - (o.h * 60 + o.m);
        }
        public String toString() {
            return String.format("%02d:%02d", h, m);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            Time[] ts = new Time[5];
            for (int i = 0; i < 5; ++i) {
                String s = sc.next();
                String[] p = s.split(":");
                ts[i] = new Time(Integer.parseInt(p[0]), Integer.parseInt(p[1]));
            }
            Arrays.sort(ts);
            System.out.println(ts[2]);
        }
    }
}

關鍵細節

• 浮點數比較用 eps 或直接 Double.compare。
• 時間比較轉換為總分鐘數 h*60+m 簡單可靠。
• 輸出格式 %02d:%02d 保證雙位數。

複雜度

常數規模（5 個元素），排序 O(1)，瞬間完成。

總結

• 幾何計算 + 多關鍵字排序的基礎綜合題。
• 時鐘夾角公式需熟記：時針 0.5°/分，分針 6°/分。
• Java Comparable 介面實現多關鍵字排序優雅簡潔。