Description

There is an analog clock with two hands: an hour hand and a minute hand. The two hands form an angle. The angle is measured as the smallest angle between the two hands. The angle between the two hands has a measure that is greater than or equal to 0 and less than or equal to 180 degrees.
Given a sequence of five distinct times written in the format hh : mm , where hh are two digits representing full hours (00 <= hh <= 23) and mm are two digits representing minutes (00 <= mm <= 59) , you are to write a program that finds the median, that is, the third element of the sorted sequence of times in a nondecreasing order of their associated angles. Ties are broken in such a way that an earlier time precedes a later time.
For example, suppose you are given a sequence (06:05, 07:10, 03:00, 21:00, 12:55) of times. Because the sorted sequence is (12:55, 03:00, 21:00, 06:05, 07:10), you are to report 21:00.

Input

The input consists of T test cases. The number of test cases (T) is given on the first line of the input file. Each test case is given on a single line, which contains a sequence of five distinct times, where times are given in the format hh : mm and are separated by a single space.

Output

Print exactly one line for each test case. The line is to contain the median in the format hh : mm of the times given. The following shows sample input and output for three test cases.

Sample Input

3
00:00 01:00 02:00 03:00 04:00
06:05 07:10 03:00 21:00 12:55
11:05 12:05 13:05 14:05 15:05

Sample Output

02:00
21:00
14:05

Source

Asia 2003（Seoul）   思路：首先要知道公式：（时间夹角） = | h * 30 - m * 5.5|

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define eps 1e-9

const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 8000 + 8;

int t;

struct node
{
    int h, m;
    double angle;
    node() : angle(0){}
}ti[8];

bool cmp(node a, node b)
{
    if(a.angle == b.angle)
        return a.h < b.h;
    else if(a.angle == b.angle && a.h == b.h)
        return a.m < b.m;
    return a.angle < b.angle;
}

int main()
{
    for(cin >> t; t--; )
    {
        for(int i = 0; i < 5; i++)
        {
            scanf("%d:%d", &ti[i].h, &ti[i].m);
            ti[i].angle = fabs((ti[i].h % 12) * 30 - 5.5 * (ti[i].m % 60));
            while(ti[i].angle > 180)ti[i].angle = fabs(360 - ti[i].angle);
        }
        sort(ti, ti + 5, cmp);
        if(ti[2].h < 10)
            printf("0%d:", ti[2].h);
        else
            printf("%d:", ti[2].h);
        if(ti[2].m < 10)
            printf("0%d\n", ti[2].m);
        else
             printf("%d\n", ti[2].m);
    }

    return 0;
}