HDU - 4458 计算几何判断点是否在多边形内

思路：将飞机看成不动的，然后枚举时间看点是否在多边形内部。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N =  + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

struct Point {

    double x, y;

    Point(double x = , double y = ) : x(x), y(y) { }

};

typedef Point Vector;

int dcmp(double x) {

    if(fabs(x) < eps) return ;

    else return x <  ? - : ;

}

Point operator + (Vector A, Vector B) {return Point(A.x + B.x, A.y + B.y);}

Point operator - (Vector A, Vector B) {return Point(A.x - B.x, A.y - B.y);}

Point operator * (Vector A, double p) {return Point(A.x * p, A.y * p);}

Point operator / (Vector A, double p) {return Point(A.x / p, A.y / p);}

bool operator < (const Vector &A, const Vector &B) {return A.y < B.y || (A.y == B.y && A.x < B.x);}

bool operator == (const Vector &A, const Point &B) {return dcmp(A.x - B.x) ==  && dcmp(A.y - B.y) == ;}

double Dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y;}

double Length(Vector A) {return sqrt(Dot(A, A));}

double Angle(Vector A, Vector B) {return acos(Dot(A, B) / Length(A) / Length(B));}

double Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;}

double Area2(Point A, Point B, Point C) {return Cross(B - A, C - A);}

double v, b, g;

Point p[N];

int n;

bool isPointOnSegment(const Point &p, const Point &a1, const Point &a2)

{

    if(dcmp(Cross(a1-p,a2-p))) return ;

    else if(dcmp(p.x-min(a1.x,a2.x))>=&&dcmp(p.x-max(a1.x,a2.x))<=

            &&dcmp(p.y-min(a1.y,a2.y))>=&&dcmp(p.y-max(a1.y,a2.y))<=) return ;

    else return ;

}

int isPointInPolygon(Point p, Point *poly, int n) {

    int wn = ;

    for(int i = ; i < n; i++) {

        if(isPointOnSegment(p, poly[i], poly[(i+)%n])) return -; //在边界上

        int k = dcmp(Cross(poly[(i+)%n]-poly[i], p-poly[i]));

        int d1 = dcmp(poly[i].y-p.y);

        int d2 = dcmp(poly[(i+)%n].y-p.y);

        if(k> && d1<= && d2>) wn++;

        if(k< && d2<= && d1>) wn--;

    }

    if(wn != ) return ; //内部

    return ; //外部

}

bool check(double t) {

    Point pos = Point(-v*t, 0.5*-g*t*t + b*t);

    if(isPointInPolygon(pos, p, n) == ) return true;

    return false;

}

int main() {

    while(scanf("%lf%lf%lf", &v, &b, &g) != EOF) {

        if(v < eps && b < eps && g < eps) break;

        scanf("%d", &n);

        for(int i = ; i < n; i++)

            scanf("%lf%lf", &p[i].x, &p[i].y);

        double ans = -;

        for(double t = ; t <= ; t += 0.001) {

            if(check(t)) {

                ans = t;

                break;

            }

        }

        if(ans < ) puts("Miss!");

        else printf("%.2f\n", ans);

    }

    return ;

}

/*

ŝ

*/