在自己的電腦測連3s都不到.....上傳卻TLE...程式碼在下幫忙想吧！都有註解 不懂可以再問.....
#include <iostream>
#include <algorithm>
using namespace std ;
/*a_num 紀錄a[]裡有幾個元素 n 題目說的n個點*/
/*m_min 原點到每個點的斜率最小值 m_max 原點到每個點的斜率最大值*/
int a_num[ 5 ] , n ;
double m_min , m_max ;
/*dot 自訂結構點的x座標與y座標*/
struct dot {
double x , y ;
}a[ 5 ][ 101 ] , e ;
/*cross 外積的副程式*/
double cross( dot& o , dot& a , dot& b )
{
return ( a . x - o . x ) * ( b . y - o . y )
- ( a . y - o . y ) * ( b . x - o . x ) ;
}
/*gt 自訂排序的規則*/
bool gt ( dot a , dot b )
{
return ( a . x < b . x ) || ( a . x == b . x && a . y < b . y ) ;
}
/*findConvexHull 弄出一個凸多邊形(順時針)*/
void findConvexHull()
{
sort( a[ 1 ] , a[ 1 ] + n , gt ) ;
int m = 0 ;
for ( int i = 0 ; i < n ; ++ i )
{
while ( m >= 2 && cross( a[ 0 ][ m - 2 ] , a[ 0 ][ m - 1 ] , a[ 1 ][ i ] ) <= 0 )
m -- ;
a[ 0 ][ m ++ ] = a[ 1 ][ i ] ;
}
for ( int i = n - 2 , t = m + 1 ; i >= 0 ; -- i )
{
while ( m >= t && cross( a[ 0 ][ m - 2 ], a[ 0 ][ m - 1 ], a[ 1 ][ i ] ) <= 0 )
m -- ;
a[ 0 ][ m ++ ] = a[ 1 ][ i ] ;
}
}
/*asas 求兩直線方程式是否有交點*/
bool asas( int i , double aa )
{
double m , b , x , y ;
if ( a[ 0 ][ ( i - 1 + n ) % n ] . x == a[ 0 ][ i ] . x )
{
x = a[ 0 ][ i ] . x ;
y = aa * x ;
e . x = x ;
e . y = y ;
if ( ( a[ 0 ][ ( i - 1 + n ) % n ] . y >= y && a[ 0 ][ i ] . y <= y )
|| ( a[ 0 ][ ( i - 1 + n ) % n ] . y <= y && a[ 0 ][ i ] . y >= y ) )
{
return true ;
}
else
{
return false ;
}
}
else
{
m = ( a[ 0 ][ ( i - 1 + n ) % n ] . y - a[ 0 ][ i ] . y )
/ ( a[ 0 ][ ( i - 1 + n ) % n ] . x - a[ 0 ][ i ] . x ) ;
b = a[ 0 ][ ( i - 1 + n ) % n ] . y - m * a[ 0 ][ ( i - 1 + n ) % n ] . x ;
x = b / ( aa - m ) ;
y = aa * b / ( aa - m ) ;
e . x = x ;
e . y = y ;
if ( ( ( a[ 0 ][ ( i - 1 + n ) % n ] . x >= x && a[ 0 ][ i ] . x <= x )
|| ( a[ 0 ][ ( i - 1 + n ) % n ] . x <= x && a[ 0 ][ i ] . x >= x ) )
&& ( ( a[ 0 ][ ( i - 1 + n ) % n ] . y >= y && a[ 0 ][ i ] . y <= y )
|| ( a[ 0 ][ ( i - 1 + n ) % n ] . y <= y && a[ 0 ][ i ] . y >= y ) ) )
{
return true ;
}
else
{
return false ;
}
}
}
/*asdf 算第m個多邊形的面積*/
double asdf( int m )
{
int i ;
double k = 0 ;
for ( i = 1 ; i < a_num[ m ] ; i ++ )
{
k += a[ m ][ i ] . x
* a[ m ][ i - 1 ] . y * 1.0 ;
}
for ( i = 0 ; i < a_num[ m ] - 1 ; i ++ )
{
k -= a[ m ][ i ] . x
* a[ m ][ i + 1 ] . y * 1.0 ;
}
if ( k < 0 )
{
k *= -1 * 1.0 ;
}
return k / 2 * 1.0 ;
}
int main ()
{
int i ;
cin >> n ;
/*讀入題目的點座標*/
for ( i = 0 ; i < n ; i ++ )
{
cin >> a[ 1 ][ i ] . x >> a[ 1 ][ i ] . y ;
}
/*弄出凸多邊形並存入a[ 0 ]*/
findConvexHull() ;
/*找出斜率的最大值與最小值並存入 m_max 和 m_min*/
m_max = m_min = a[ 0 ][ 0 ] . y
/ a[ 0 ][ 0 ] . x * 1.0 ;
for ( i = 0 ; i < n ; i ++ )
{
double qw = a[ 0 ][ i ] . y
/ a[ 0 ][ i ] . x * 1.0 ;
if ( m_max < qw )
{
m_max = qw ;
}
if ( m_min > qw )
{
m_min = qw ;
}
}
/*想法：在最大值與最小值之間切下去，
如果某一邊面積比較大就往那邊切，
直到答案出來為止。*/
double m = ( m_max + m_min ) / 2 ;
for ( ; m != m_max && m != m_min ; )
{
a_num[ 1 ] = a_num[ 2 ] = 0 ;
/*以斜率 m 切下去分成上下兩區塊 e 兩直線交點*/
for ( i = 0 ; i < n ; i ++ )
{
if ( asas( i , m ) )
{
a[ 1 ][ a_num[ 1 ] ++ ] = e ;
a[ 2 ][ a_num[ 2 ] ++ ] = e ;
a[ 2 ][ a_num[ 2 ] ++ ] = a[ 0 ][ i ++ ] ;
break ;
}
a[ 1 ][ a_num[ 1 ] ++ ] = a[ 0 ][ i ] ;
}
for ( ; i < n ; i ++ )
{
if ( asas( i , m ) )
{
a[ 2 ][ a_num[ 2 ] ++ ] = e ;
a[ 1 ][ a_num[ 1 ] ++ ] = e ;
a[ 1 ][ a_num[ 1 ] ++ ] = a[ 0 ][ i ++ ] ;
break ;
}
a[ 2 ][ a_num[ 2 ] ++ ] = a[ 0 ][ i ] ;
}
for ( ; i < n ; i ++ )
{
a[ 1 ][ a_num[ 1 ] ++ ] = a[ 0 ][ i ] ;
}
a[ 2 ][ a_num[ 2 ] ++ ] = a[ 2 ][ 0 ] ;
a[ 1 ][ a_num[ 1 ] ++ ] = a[ 1 ][ 0 ] ;
/*將上面的區塊存入 a[ 3 ] 下面區塊存入 a[ 4 ]*/
if ( a[ 2 ][ 0 ] . y < m * a[ 2 ][ 0 ] . x
|| a[ 2 ][ 1 ] . y < m * a[ 2 ][ 1 ] . x )
{
a_num[ 3 ] = a_num[ 1 ] ;
a_num[ 4 ] = a_num[ 2 ] ;
for ( i = 0 ; i < a_num[ 3 ] ; i ++ )
{
a[ 3 ][ i ] = a[ 1 ][ i ] ;
}
for ( i = 0 ; i < a_num[ 4 ] ; i ++ )
{
a[ 4 ][ i ] = a[ 2 ][ i ] ;
}
}
else
{
a_num[ 4 ] = a_num[ 1 ] ;
a_num[ 3 ] = a_num[ 2 ] ;
for ( i = 0 ; i < a_num[ 4 ] ; i ++ )
{
a[ 4 ][ i ] = a[ 1 ][ i ] ;
}
for ( i = 0 ; i < a_num[ 3 ] ; i ++ )
{
a[ 3 ][ i ] = a[ 2 ][ i ] ;
}
}
/*決定要往下還是往上切*/
if ( asdf( 3 ) > asdf( 4 ) )
{
m_min = m ;
m = ( m + m_max ) / 2 ;
}
else
{
m_max = m ;
m = ( m + m_min ) / 2 ;
}
}
/*終於可以輸出答案嚕 ^^ */
printf( "%.4lf\n" , m ) ;
}