http://acm.hdu.edu.cn/showproblem.php?pid=3437AC牛的题目,精度比较恶心,最后一组数据一个误差是0.00006 我精度用了1e-8,而标程是1e-4,卡死在最后一组数据上了。。。 这题看起来是三维的几何,其实完全可以压缩到二维来做。
1 // Author : AmazingCaddy 2 // 3 #include<iostream> 4 #include<cstdio> 5 #include<cstring> 6 #include<algorithm> 7 #include<vector> 8 #include<cmath> 9 #include<complex> 10 using namespace std; 11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 12 typedef complex<double> point; 13 const double eps = 1e-4; 14 const double inf = 1e20; 15 const double pi = acos( -1.0 ); 16 const double g = 9.18; 17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) double operator ^ ( const point p1, const point p2 ) { return imag( conj( p1 ) * p2 ); } 19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) double operator & ( const point p1, const point p2 ) { return real( conj( p1 ) * p2 ); } 20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int dblcmp( double x ) { return ( x < -eps ? -1 : x > eps ); } 21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 22 struct line 23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 24 point a, b; 25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) line( ) { } 26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) line( point u, point v ) : a( u ) , b( v ) { } 27 }; 28![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 29 struct POLY 30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 31 point p[12]; 32 int n, type; 33 double h, k; 34 }poly[12]; 35![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) bool cmp( const POLY & a, const POLY & b ) { return ( a.h == b.h && a.type < b.type ) || a.h > b.h; } 37![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 38 point operator*( line l0, line l1 ) 39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 40 double t = l0.a - l1.a^ l0.b - l1.a; 41 double s = l0.b - l1.b^ l0.a - l1.b; 42 return l1.a + ( l1.b - l1.a ) * t / ( t + s ); 43 } 44![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 45 // 不是逆时针,转化成逆时针的 46 void changeclockwise( POLY & P ) 47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 48 int pn = P.n; 49 if( ( P.p[1] - P.p[0] ^ P.p[2] - P.p[0] ) < 0 ) 50 for( int i = 0; i < pn / 2; i++ ) 51 swap( P.p[i], P.p[pn-1-i] ); 52 } 53![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 54 bool point_on_segment( const point & p, const line & l ) 55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 56 if( dblcmp( l.a - p ^ l.b - p ) ) return false; 57 if( dblcmp( l.a - p & l.b - p ) <= 0 ) return true; 58 return false; 59 } 60![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 61 bool segment_cross( const line & l1, const line l2 ) 62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 63 point p1 = l1.a, p2 = l1.b, p3 = l2.a, p4 = l2.b; 64 if( ( dblcmp( p2 - p1 ^ p3 - p1 ) ^ dblcmp( p2 - p1 ^ p4 - p1 ) ) == -2 && 65 ( dblcmp( p4 - p3 ^ p1 - p3 ) ^ dblcmp( p4 - p3 ^ p2 - p3 ) ) == -2 ) 66 return true; 67 return false; 68 } 69![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 70 bool PointInPoly( const point & p, const POLY & Q ) 71![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 72 int qn = Q.n; 73 double area1 = 0, area2 = 0; 74 for( int i = 0; i < qn; i++ ) 75 area1 = area1 + ( Q.p[i] ^ Q.p[i+1] ); 76 for( int i = 0; i < qn; i++ ) 77 area2 = area2 + fabs( Q.p[i] - p ^ Q.p[i+1] - p ); 78 if( dblcmp( fabs( area1 ) - area2 ) == 0 ) 79 return true; 80 return false; 81 } 82![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 83 point seg_cross_poly( line l, const POLY & Q ) 84![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 85 int qn = Q.n; 86 point s; 87 for( int i = 0; i < qn; i++ ) 88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 89 line l1 = line( Q.p[i], Q.p[i+1] ); 90 if( dblcmp( l.a - l.b ^ l1.a - l1.b ) != 0 ) 91![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 92 s = l * l1; 93 if( point_on_segment( s, l1 ) && dblcmp( s - l.a & l.b - l.a ) > 0 && !point_on_segment( s, l ) ) 94 break; 95 } 96 } 97 return s; 98 } 99![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 100 void solve( ) 101![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 102 int n; 103 double vx, vy, H, x, y,TIME; 104 scanf("%lf%lf%lf",&vx,&vy,&H); 105 point v( vx, vy ), s( 0, 0 ); // v 速度矢量,s 位移矢量 106 point s0; 107 scanf("%d",&n); 108 for( int i = 0; i < n; i++ ) 109![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 110 scanf("%lf%d",&poly[i].h,&poly[i].n); 111 for( int j = 0; j < poly[i].n; j++ ) 112![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 113 scanf("%lf%lf",&x,&y); 114 poly[i].p[j] = point( x, y ); 115 } 116 changeclockwise( poly[i] ); 117 poly[i].p[poly[i].n] = poly[i].p[0]; 118 scanf("%d%lf",&poly[i].type,&poly[i].k); 119 } 120![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 121 poly[n].n = 4; poly[n].h = 0; poly[n].type = 3; poly[n].k = 0; 122 poly[n].p[0] = point( 1e8, 1e8 ); 123 poly[n].p[1] = point( -1e8, 1e8 ); 124 poly[n].p[2] = point( -1e8, -1e8 ); 125 poly[n].p[3] = point( 1e8, -1e8 ); 126 poly[n].p[4] = point( 1e8, 1e8 ); 127 n++; 128 sort( poly, poly + n, cmp ); 129![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 130 if( dblcmp( H ) < 0 ) 131![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 132 printf("Forever!\n"); 133 return ; 134 } 135 TIME = 0.0; 136 for( int i = 0; i < n; i++ ) 137![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 138 double h = poly[i].h; 139 double k = poly[i].k; 140 if( h == 0 ) 141![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 142 TIME += sqrt( 2 * ( H - h ) / g ); 143 printf("%.2lf\n",TIME); 144 return ; 145 } 146 if( H < h ) continue; 147 double time = sqrt( 2 * ( H - h ) / g ); 148 s0 = s + v * time; 149 if( PointInPoly( s0, poly[i] ) ) 150![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 151 s = s0; 152 TIME += time; 153 H = h; 154 switch( poly[i].type ) 155![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 156 case 0: 157 v = v * point( cos( k ), sin( k ) ); 158 break; 159![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 160 case 1: 161 v = point( k, imag( v ) ); 162 break; 163![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 164 case 2: 165 v = point( real( v ), k ); 166 break; 167 } 168 if( dblcmp( abs( v ) ) == 0 ) 169![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 170 printf("Forever!\n"); 171 return ; 172 } 173 point z = seg_cross_poly( line( s, s + v ), poly[i] ); 174 TIME = TIME + abs( z - s ) / abs( v ); 175 s = z; 176 } 177 } 178 } 179![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 180 int main( ) 181![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 182 int t; 183 //freopen("in","r",stdin); 184 //freopen("out.txt","w",stdout); 185 scanf("%d",&t); 186 for( int i = 1; i <= t; i++ ) 187![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 188 printf("Case %d: ",i); 189 solve( ); 190 } 191 return 0; 192 }
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
常用链接
留言簿
随笔分类
随笔档案
传送门
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|