http://acm.sgu.ru/problem.php?contest=0&problem=124
计算几何题，判断一个点是在所给的简单多边形内部，外部或是边界上。判断的方法：
从测试点任意引出射线，与多边形的边相交的交点总数如果是奇数，则在多边形内部。如果是偶数，则在多边形内部。
边界情况的考虑：
如果引出的射线正好通过多边形的某个顶点，那么应该是算1个交点还是2个交点。可以这样判断，如果顶点所在的两条线段处在射线的同侧，则算为2个点，如果是不同侧，则算作一个点。对于引出的射线恰好与多边形的某条边重合的情况也是类似的判断。
为什么可以按照上面判断，一开始我也是不清楚，搜到了WindyWinter牛的解题报告。里面提到了另一种判断边界情况的方法。"解决特殊问题的办法基于这样一个思想——对于不在多边形边上的待测点，把它向上（或向下）移动一个极小量，是不会改变它与多边形的位置关系的。但是移动以
后却带来巨大的好处，不会再出现这么多麻烦的特殊情况了。另外，由于移动的是“极小量”，所以不用担心把原本不特殊的情况移动成了特殊情况。
"(From WindyWinter's blog)。所以就可以解释为什么可以通过同侧不同侧来判断了，比如说不同侧的情况，将测试点稍微上移，那么由于线段在不同侧，所以射线将只与其中一条线段相交，所以应该算一个交点。编程中实现的话还是用移动一个极小量来实现简单。
另外题目中提到了所有的边都与坐标轴平行，所以判断与射线的相交也不需要用叉积判断。
submit1: WA on test 5. 其中一个语句的x和y弄混了
submit2: AC
#include <stdio.h>
#include <stdbool.h>
typedef struct tagPoint {
int x;
int y;
} Point;
bool OnBorder(Point* a, Point* b, Point* p);
bool cross(Point* a, Point* b, Point* c);
int main(void) {
int n;
scanf ("%d", &n);
Point edge[10000][2], P;
int i;
for (i = 0; i < n; ++i) {
scanf ("%d%d%d%d", &edge[i][0].x, &edge[i][0].y, &edge[i][1].x, &edge[i][1].y);
}
scanf ("%d%d", &P.x, &P.y);
int count = 0;
for (i = 0; i < n; ++i) {
if (OnBorder(&edge[i][0], &edge[i][1], &P)) {
printf ("BORDER\n");
return 0;
}
if (cross(&edge[i][0], &edge[i][1], &P)) {
count++;
}
}
if (count&1) {
printf ("INSIDE\n");
} else {
printf ("OUTSIDE\n");
}
return 0;
}
bool OnBorder(Point* a, Point* b, Point* c) {
if (a->y == b->y && ((a->x <= c->x && c->x <= b->x) || (a->x >= c->x && c->x >= b->x))) {
return (a->y == c->y) ? true: false;
}
if (a->x == c->x && ((a->y <= c->y && c->y <= b->y) || (a->y >= c->y && c->y >= b->y))) {
return true;
}
return false;
}
bool cross(Point* a, Point* b, Point* c) {
if (((a->y > c->y && b->y <= c->y) || (a->y <= c->y && b->y > c->y)) && c->x < a->x) {
return true;
}
return false;
}