题目地址：http://poj.org/problem?id=3335

题目：

顺时针（虽然题目没有特别讲明）给出多边形各边上的点，观众坐在多边形的边上，问是否能够在多边形内找到一点放置计分牌，使得在多边形边上坐着的所有观众都能看到这个计分牌。可以的话输出YES，否则NO

注意：Note that if the line of sight of a spectator is tangent to the polygon boundary (either in a vertex or in an edge), he can still view the scoreboard.

 

解题思路：

问题转化为求半平面交，判断有无半平面交。注意求半平面交的时候边是逆时针顺序！

题目中特意说明：如果观察者的视线与多边形边界相切(无论是在顶点还是在边缘)，他仍然可以查看记分牌。这其实说明计分牌可以放在顶点上，如下图：最终可以确定一个点使得所有观众能看到计分牌，但是这个点在顶点上，该顶点上的观众可以将视线斜视看到计分牌（也许是这么解释。。。或者不考虑计分牌的体积。。。反正不这么考虑就wa了）

图源：https://www.cnblogs.com/JasonCow/p/6636442.html

数据：17 2 -1 2 -2 1 -2 0 -1 -1 -2 -2 -2 -2 -1 -1 0 -2 1 -2 2 -1 2 0 1 1 2 3 2 3 1 2 1 1 0

所以OnLeft函数就要改为：

bool OnLeft(Line L, Point p)
{
    return dcmp(Cross(L.v, p-L.p)) > 0 || dcmp(Cross(L.v, p-L.p)) == 0;
} 

最终的半平面交如果是个区域的话，至少有三个顶点，如果是点的话，至少被访问过三次，所以只有半平面交函数的返回值m≥3时才会输出YES

 

ac代码：

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 110;
struct Point
{
    double x,y;
    Point(double x=0, double  y=0):x(x),y(y){}
};
typedef Point Vector;
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x > 0 ? 1 : -1;
}
Vector operator + (Vector a, Vector b)//向量加法
{
    return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b)//向量减法
{
    return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, double p)//向量数乘
{
    return Vector(a.x * p, a.y * p);
}
Vector operator / (Vector a, double p)//向量数除
{
    return Vector(a.x / p, a.y / p);
}
double Cross(Vector a, Vector b)//外积
{
    return a.x * b.y - a.y * b.x;
}
double Dot(Vector a, Vector b)//点积
{
    return a.x * b.x + a.y * b.y;
}
double Length(Vector a)//模
{
    return sqrt(Dot(a, a));
}

struct Line{
    Point p;//直线上任意一点
    Vector v;//方向向量
    double ang;//极角
    Line(){}
    Line(Point p, Vector v):p(p),v(v){ang = atan2(v.y,v.x);}
    friend bool operator < (Line a, Line b)
    {
        return a.ang < b.ang;
    }
};
bool OnLeft(Line L, Point p)
{
    return dcmp(Cross(L.v, p-L.p)) > 0 || dcmp(Cross(L.v, p-L.p)) == 0;
}
Point GetIntersection(Line a, Line b)
{
    Vector u = a.p-b.p;
    double t = Cross(b.v,u)/Cross(a.v,b.v);
    return a.p+a.v*t;
}
int HalfplaneIntersection(Line *L, int n, Point * poly)
{
    sort(L, L+n);//按极角排序
    int first, last;//指向双端队列的第一个元素和最后一个元素
    Point *p = new Point[n];//p[i]为q[i]和q[i+1]的交点
    Line *q = new Line[n];//双端队列
    q[first=last=0] = L[0];
    for(int i = 1; i < n; i++)
    {
        while(first < last && !OnLeft(L[i], p[last-1])) last--;
        while(first < last && !OnLeft(L[i], p[first])) first++;
        q[++last] = L[i];
        if(fabs(Cross(q[last].v,q[last-1].v)) < eps)//两向量平行且同向，取内侧的一个
        {
            last--;
            if(OnLeft(q[last],L[i].p)) q[last] = L[i];
        }
        if(first < last) p[last-1] = GetIntersection(q[last-1],q[last]);
    }
    while(first < last && !OnLeft(q[first], p[last-1])) last--;//删除无用平面
    if(last - first <= 1) return 0;
    p[last] =GetIntersection(q[last], q[first]);//首位半平面的交点
    int m = 0;
    for(int i = first; i <= last; i++) poly[m++] = p[i];
    return m;

}
Point p[maxn], poly[maxn];//p存输入的点， poly存半平面交上的点
Line L[maxn];
int t, n;
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) scanf("%lf %lf", &p[i].x, &p[i].y);
        for(int i = n-1; i >= 0; i--) L[n-i-1] = Line(p[i], p[(i-1+n)%n]-p[i]);
        int m = HalfplaneIntersection(L, n, poly);
        if(m < 3) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}