http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=2830題目大意：空中有很多豎直的門(mén)，一個(gè)點(diǎn)以V0的初速度拋出，忽略空氣阻力，重力加速度為10m/s
2,求此點(diǎn)最多能穿過(guò)幾個(gè)門(mén)。
解法：對(duì)于每個(gè)門(mén)，根據(jù)斜拋運(yùn)動(dòng)，解出初速度與x軸的夾角范圍，然后求出重疊次數(shù)最大的區(qū)域，輸出該次數(shù)。
eoj 2830
1
#include <cstdio>
2#include <iostream>
3#include <cstring>
4#include <complex>
5#include <string>
6#include <algorithm>
7#include <vector>
8#include <cmath>
9using namespace std;
10
11const int maxn = 20005;
12const double eps = 1e-8;
13const double inf = 1e20;
14const double pi = acos( -1.0 );
15const double g = 10.0;
16
17struct node
18
{
19
double angle1, angle2;
20
}ang[ maxn << 1 ];
21
22int D( double x ) { return ( x < -eps ? -1 : x > eps ); }
23
24bool cmp( const node & a, const node & b )
25{
26 if( D( a.angle1 - b.angle1 ) != 0 ) return a.angle1 < b.angle1;
27 return D( a.angle2 - b.angle2 ) < 0;
28}
29
30
31//double y1[ maxn ], y2[ maxn ];
32//double x[ maxn ];
33
34int main(int argc, char *argv[])
35{
36 int cas, v0, n;
37 double a, b, c, t, x, y1, y2, data;
38 double angle1, angle2, angle3, angle4;
39 scanf("%d",&cas);
40 while( cas-- )
41
{
42 scanf("%lf%d",&v0,&n);
43 int len = 0;
44 for( int i = 0; i < n; i++ )
45 {
46 scanf("%lf%lf%lf",&x,&y1,&y2);
47 a = g * ( x / v0 ) * ( x / v0 ) / 2.0 ;
48 b = -x;
49 c = y1 + a;
50 data = b * b - 4 * a * c ;
51 if( D( data ) >= 0 )
52 {
53 if( data < 0 ) data = 0;
54 t = sqrt( data );
55 angle1 = ( -b - t ) / 2.0 / a ;
56 angle2 = ( -b + t ) / 2.0 / a ;
57
}
58 else continue;
59 a = g * ( x / v0 ) * ( x / v0 ) / 2.0 ;
60 b = -x ;
61 c = y2 + a ;
62 data = b * b - 4 * a * c ;
63 if( D( data ) >= 0 )
64 {
65 if( data < 0 ) data = 0;
66 t = sqrt( data );
67 angle3 = ( -b - t ) / 2.0 / a ;
68 angle4 = ( -b + t ) / 2.0 / a ;
69 ang[ len ].angle1 = angle1;
70 ang[ len ].angle2 = angle3;
71 len++;
72 ang[ len ].angle1 = angle4;
73 ang[ len ].angle2 = angle2;
74 len++;
75 }
76 else
77 {
78 ang[ len ].angle1 = angle1;
79 ang[ len ].angle2 = angle2;
80 len++;
81 }
82
83 }
84 sort( ang, ang + len, cmp );
85 double st = ang[ 0 ].angle1, ed = ang[ 0 ].angle2;
86 int ans = 1, cnt = 0;
87 for( int i = 1; i < len; i++ )
88 {
89 if( D( ang[ i ].angle1 - ed ) > 0 )
90 {
91 if( cnt > ans ) ans = cnt;
92 st = ang[ i ].angle1, ed =ang[ i ].angle2;
93 }
94 else
95 {
96 cnt++;
97 }
98 }
99 printf("%d\n",ans);
100 }
101 return 0;
102}
103