题目链接：
UVALive 7004 Inside, Outside or On
题意：
顺时针给出多边形的顶点，另给出一点，判断额外点是在多边形边上还是多边形内部，还是多边形外部？
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
const double eps = 1e-8;
const int MAX_N=1010;int T,n,m;//判断浮点数x的符号
int sgn(double x)
{if(fabs(x) < eps) return 0;else if(x < 0) return -1;else return 1;
}
struct Point{double x,y;Point () {}Point (double x,double y) : x(x),y(y) {}Point operator + (const Point& rhs) const {return Point(x+rhs.x,y+rhs.y);}Point operator - (const Point& rhs) const {return Point(x-rhs.x,y-rhs.y);}Point operator * (const double d) const {return Point(d*x,d*y);}bool operator == (const Point& rhs) const {if(sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0) return true;else return false;}double dot(const Point& rhs) const {return x*rhs.x+y*rhs.y;}double cross(const Point& rhs) const{return (x*rhs.y-y*rhs.x);}
}point[MAX_N];bool on_seg(Point p1,Point p2,Point p) //判断p是否在线段p1--p2上
{return (p1 - p).cross(p2 - p) == 0 && (p1 - p).dot(p2 - p) <= 0;
}//判断多边形和点的关系: 3点在顶点上,2在边上,1在内部,0在外部
int relation_with_point(Point q, int n)
{for(int i = 1; i <= n; i++){if(q == point[i]) return 3;}point[n + 1] = point[1];for(int i = 1; i <= n; i++){if(on_seg(point[i], point[i + 1], q)) return 2;}int cnt = 0;for(int i = 1; i <= n; i++){int j = i + 1;int k = sgn((q - point[j]).cross(point[i] - point[j]));int u = sgn(point[i].y - q.y);int v = sgn(point[j].y - q.y);if(k > 0 && u < 0 && v >= 0) cnt++;if(k < 0 && v < 0 && u >= 0) cnt--;}return cnt != 0;
}int main()
{//freopen("000.in", "r", stdin);scanf("%d",&T);while(T--){scanf("%d%lf%lf",&m, &point[0].x, &point[0].y);for(int i = 0; i < m; i++){if(i) printf(" ");scanf("%d",&n);for(int j = 1; j <= n; j++){scanf("%lf%lf", &point[j].x, &point[j].y);}int ans = relation_with_point(point[0], n);if(ans == 3 || ans == 2) printf("0");else if(ans == 1) printf("1");else printf("2");}printf("\n");}return 0;
}