[UVa] 10195 - The Knights Of The Round Table

題目網址: http://goo.gl/RhW9KM

題意:
(from luckycat)


解法: 用海龍公式算出三角形面積，接著三角形面積又等於 (a+b+c)*r/2， r 就是內接圓半徑。

TAG: Math

注意: 三角形三邊長都有可能為 0 !

程式碼:

	/**
	* Tittle: 10191 - Longest Nap
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/09
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	class Time {
	public:
	int from, to;
	Time( int _f = 0, int _t = 0 ): from(_f), to(_t) {}
	const bool operator<( const Time &op ) const {
	return from<op.from;
	}
	};
	// declarations
	int n;
	Time t[N];
	char buf[3*N];
	int maxi, maxv;
	int day = 1;
	// functions
	// main function
	int main( void )
	{
	int a, b, c, d;
	// input
	while( scanf( "%d", &n )==1 ) {
	n += 2;
	t[1] = Time( 0, 10*60 );
	FOR( i, 2, n-1 ) {
	scanf( "%d:%d %d:%d", &a, &b, &c, &d );
	t[i].from = a*60+b;
	t[i].to = c*60+d;
	gets(buf);
	}
	t[n] = Time( 18*60, 18*60 );
	// solve
	sort( t+2, t+n );
	// FOR( i, 1, n ) printf( "(%d,%d)\n", t[i].from, t[i].to );
	maxi = 1;
	maxv = t[2].from-t[1].to;
	FOR( i, 2, n-1 )
	if( maxv < (t[i+1].from-t[i].to) ) {
	maxv = t[i+1].from-t[i].to;
	maxi = i;
	}
	// output
	printf( "Day #%d: the longest nap starts at ", day++ );
	printf( "%02d:%02d", t[maxi].to/60, t[maxi].to%60 );
	printf( " and will last for " );
	if( maxv >= 60 )
	printf( "%d hours and ", maxv/60 );
	printf( "%d minutes.\n", maxv%60 );
	}
	return 0;
	}

view raw 10191 - Longest Nap.cpp hosted with ❤ by GitHub