2015
07-16

# Shoot the Airplane

XXX is playing an interesting game which is based on a 2D plane. In this game, he is required to shoot an airplane. The airplane flies horizontally. The shape of it can be regarded as a simple polygon. Player has to shoot at point (0, 0) upward vertically. Because the bullet is very small, it can be regarded as a point. The airplane is hit only if the bullet goes into the airplane. The airplane is not hit if the bullet only touches the edge of the airplane. The gravity should be considered. The acceleration of gravity is g and its direction is downward vertically. So the speed of the bullet may be change during flying. But the speed of airplane is constant because it has engines. XXX wants to know the time it takes the bullet to hit the airplane after shooting.

There are multiple cases.
In each case, there are three integers v (-10<= v <= 10), b (1 <= b <= 10), g (0 <= g <= 10) in the first line. v denotes the speed of airplane. The flying direction is from left to right if v is positive and the direction is from right to left if v is negative. b denotes the initial speed of bullet. g is the acceleration of gravity. Then the input will describe the position of the airplane when XXX shoots. In the second line, there is one integer n (3 <= n <= 20) which represents the number of vertexes of the airplane (polygon). In each of the next n lines, there are two integers x (-100 <= x <= 100), y (0 <y<= 100) which give the position of a vertex in order. There is a blank line after each case. The input ends with 0 0 0.

There are multiple cases.
In each case, there are three integers v (-10<= v <= 10), b (1 <= b <= 10), g (0 <= g <= 10) in the first line. v denotes the speed of airplane. The flying direction is from left to right if v is positive and the direction is from right to left if v is negative. b denotes the initial speed of bullet. g is the acceleration of gravity. Then the input will describe the position of the airplane when XXX shoots. In the second line, there is one integer n (3 <= n <= 20) which represents the number of vertexes of the airplane (polygon). In each of the next n lines, there are two integers x (-100 <= x <= 100), y (0 <y<= 100) which give the position of a vertex in order. There is a blank line after each case. The input ends with 0 0 0.

-10 10 2
9
6 9
10 9
10 16
25 16
25 20
10 20
10 27
6 27
-10 18

-10 10 2
9
6 9
10 9
10 16
20 16
20 20
10 20
10 27
6 27
-10 18

0 0 0

2.00
Miss!

1.题目描述：点击打开链接

2.解题思路：本题利用运动的相对性解决。可以假设飞机固定不动，那么子弹相当于还有一个水平分量，只不过方向是-v。这样，问题就转化为一个动点什么时候到达一个多边形内部的问题了。不过本题有一个细节就是g可能等于0，因此要分匀变速运动和匀速运动2种情况求出最大可能的子弹飞行时间。另外一个细节就是本题对精度要求比较高，建议判断点是否在线段上改为利用坐标的差值来判断，避开使用Dot函数。

3.代码：

#include<iostream>
#include<algorithm>
#include<cassert>
#include<string>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<functional>
using namespace std;

#define me(s)  memset(s,0,sizeof(s))
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//typedef pair <int, int> P;

const double PI=acos(-1.0);
const double eps=1e-10;

int dcmp(double x)
{
if(fabs(x)<eps)return 0;
return x<0?-1:1;
}
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator+(const Point&p){return Point(x+p.x,y+p.y);}
Point operator-(const Point&p){return Point(x-p.x,y-p.y);}
Point operator*(double p){return Point(x*p,y*p);}
Point operator/(double p){return Point(x/p,y/p);}

};

typedef Point Vector;

double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double Length(Vector a){return sqrt(Dot(a,a));}
double Angle(Vector a,Vector b){return acos(Dot(a,b)/Length(a)/Length(b));}

bool OnSegment(Point p,Point a,Point b)
{
if(dcmp(Cross(p-a,p-b)))return 0;
return dcmp(a.x-p.x)*dcmp(b.x-p.x)<=0&&dcmp(a.y-p.y)*dcmp(b.y-p.y)<=0; //利用dcmp判断，避免使用Dot
}

typedef vector<Point> Polygon;

int isPointInPolygon(Point p,Polygon poly)
{
int wn=0;
int n=poly.size();
for(int i=0;i<n;i++)
{
if(OnSegment(p,poly[i],poly[(i+1)%n]))return 0;
int k=dcmp(Cross(poly[(i+1)%n]-poly[i],p-poly[i]));
int d1=dcmp(poly[i].y-p.y);
int d2=dcmp(poly[(i+1)%n].y-p.y);
if(k>0&&d1<=0&&d2>0)wn++;
if(k<0&&d2<=0&&d1>0)wn--;
}
return wn;
}

double v,b,g;
int n;

int main()
{
while(~scanf("%lf%lf%lf",&v,&b,&g))
{
if(v==0&&b==0&&g==0)break;
scanf("%d",&n);
Polygon p;
double my=0.0,x,y;
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&x,&y);
my=max(my,y);
p.push_back(Point(x,y));
}
int ok=0;
double T=dcmp(g)?2.0*b/g:my/b; //分2种情况
for(double t=0.0;t<=T;t+=0.001)
{
Point tmp(-v*t,b*t-0.5*g*t*t);
if(isPointInPolygon(tmp,p))
{
printf("%.2lf\n",t);
ok=1;
break;
}
}
if(!ok)puts("Miss!");
}
}