题目大意：给出一个多边形的每一条边（顺序随机），判断一个点与多边形的位置关系（在外，在内，在多边形上）。
　　判断点与多边形的简单算法有射线法和环顾法（转角法）两类。具体的介绍请查阅《算法艺术与信息学竞赛》。这里简单介绍射线法。
　　以待判断的点为端点，向任意方向作一条射线，如果这条射线与多边形的边有奇数个交点，那么这个点就在多边形内，如果有偶数个交点，就在多边形外。方法看似简单，但特殊情况很多，如下图：
sgu124
　　a,b两图都是非常“规范”的情况，而c,d图出现问题——射线与多边形的交点恰是多边形的顶点，算作几个交点？如果按照我们的本意，这种情况应该算作1个交点。对于e,f两图而言，无论把一条与射线部分重合的边当作几个交点，都无法对两者进行区分。
　　解决特殊问题的办法基于这样一个思想——对于不在多边形边上的待测点，把它向上（或向下）移动一个极小量，是不会改变它与多边形的位置关系的。但是移动以后却带来巨大的好处，不会再出现这么多麻烦的特殊情况了。另外，由于移动的是“极小量”，所以不用担心把原本不特殊的情况移动成了特殊情况。
　　上移极小量的具体实现：如果是向上移动，而射线又与x轴平行，那么只要多边形的边上较高的顶点高于射线，较低的顶点在射线上或低于射线，就可以认为这条边“跨越”了射线，否则，即是不跨越。只要再判断射线是否“跨越”这条边，就知道有没有交点了。
　　Submit 1: WA on 7。判断射线是否跨越边的地方乘法乘爆了。
　　Submit 2: WA on 7。很郁闷，没查出来。做到这里才发现，题目中有说明多边形的边都是平行于坐标轴的……根本用不着计算几何的方法判断是否相交！
改写算法，继续。
　　Submit 3: WA on 10。没有找到错，看一下别人的解题报告和程序。没从别人那看出来，自己想起来了：改写判断相交的时候，忘了“上移极小量”了……但表面现象是<写成了<=。没话说，请客，AC后请faster_noi和MaShuo吧。
　　Submit 4: TLE on 25。……不会又是iostream吧？
　　Submit 5: AC。巨大的无奈了……改stdio后，时间从625ms(TLE on 25)下降到63ms(AC)。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

//AC
#include <cstdio>
using namespace std;
 
struct point
{
    long x,y;
};
 
inline bool horiz(const point &p1,const point &p2) /* see if seg[p1,p2] is parallel with x axes */
{
    return p1.y==p2.y;
}
 
bool onborder(const point &p1,const point &p21,const point &p22)
{
    const point *higher,*lower;
    if (horiz(p21,p22))
    {
        higher=p21.x>p22.x?&p21:&p22; lower=p21.x>p22.x?&p22:&p21;
        return (p1.y==p21.y) && (lower->x<=p1.x) && (higher->x>=p1.x);
    }
    else
    {
        higher=p21.y>p22.y?&p21:&p22; lower=p21.y>p22.y?&p22:&p21;
        return (p1.x==p21.x) && (lower->y<=p1.y) && (higher->y>=p1.y);
    }
}
 
bool cross(const point &p11,const point &p12,const point &p2)
{
    const point *higher,*lower;
    higher=p11.y>p12.y?&p11:&p12; lower=p11.y>p12.y?&p12:&p11;
    return (!horiz(p11,p12)) && (p2.x<p11.x) && (lower->y<=p2.y) && (higher->y>p2.y);
}
 
int main()
{
    long n,c(0);
    point edges[10000][2];
    point testpoint;
    scanf("%d\n",&n);
    for (long i=0;i<n;++i)
        scanf("%d %d %d %d\n",&edges[i][0].x,&edges[i][0].y,&edges[i][1].x,&edges[i][1].y);
    scanf("%d %d",&testpoint.x,&testpoint.y);
    for (long i=0;i<n;++i)
    {
        if (onborder(testpoint,edges[i][0],edges[i][1]))
        {
            printf("BORDER\n"); return 0;
        }
        else if (cross(edges[i][0],edges[i][1],testpoint)) ++c;
    }
    if (c & 1) printf("INSIDE\n");
    else printf("OUTSIDE\n");
    return 0;
}