SGU 124 Broken line(计算几何)

Description:

There is a closed broken line on a plane with sides parallel to coordinate axes, without self-crossings and self-contacts. The broken line consists of K segments. You have to determine, whether a given point with coordinates (X0,Y0) is inside this closed broken line, outside or belongs to the broken line.

Input:

The first line contains integer K (4 Ј K Ј 10000) - the number of broken line segments. Each of the following N lines contains coordinates of the beginning and end points of the segments (4 integer xi1,yi1,xi2,yi2; all numbers in a range from -10000 up to 10000 inclusive). Number separate by a space. The segments are given in random order. Last line contains 2 integers X0 and Y0 - the coordinates of the given point delimited by a space. (Numbers X0, Y0 in a range from -10000 up to 10000 inclusive).

Output:

The first line should contain:

INSIDE - if the point is inside closed broken line,

OUTSIDE - if the point is outside,

BORDER - if the point belongs to broken line.

Sample Input:

4
0 0 0 3
3 3 3 0
0 3 3 3
3 0 0 0
2 2

Sample Output:

INSIDE

题目链接

题意为判断一点与多边形的关系（在多边形内部、外部或者边界）

首先判断点是否在多边形边界上（这很容易），之后再用射线法进行判断

射线法为从判断点引一条水平射线，判断与多边形的边界交点数量，若为偶数则在多边形外部，若为奇数则在多边形内部

其中又有一些特殊情况，首先跳过多边形与 $轴平行的边界线，之后对于射线与多边形顶点相交的情况其在判断与多边形边界线段是否相交时按照一定规则只在其中一顶点相交时才判断相交，在另一顶点相交时不判断相交$

可根据下图理解射线法的原理（红***域为多边形，两条射线为 $）$

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db inf = 1e20;
const int maxn = 1e4 + 5;
const db eps = 1e-9;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
int Cmp(db Key1, db Key2) {return Sgn(Key1 - Key2);}
struct Point {db X, Y;};
typedef Point Vector;
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};}
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};}
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;}
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;}
struct Line {Point S, T;};
typedef Line Segment;
typedef Line Ray;
bool IsPointOnSeg(Point Key1, Segment Key2) {
    return Sgn((Key1 - Key2.S) ^ (Key2.T - Key2.S)) == 0 && Sgn((Key1 - Key2.S) * (Key1 - Key2.T)) <= 0;
}
bool IsSegInterSeg(Segment Key1, Segment Key2) {
    return
        max(Key1.S.X, Key1.T.X) >= min(Key2.S.X, Key2.T.X) &&
        max(Key2.S.X, Key2.T.X) >= min(Key1.S.X, Key1.T.X) &&
        max(Key1.S.Y, Key1.T.Y) >= min(Key2.S.Y, Key2.T.Y) &&
        max(Key2.S.Y, Key2.T.Y) >= min(Key1.S.Y, Key1.T.Y) &&
        Sgn((Key2.S - Key1.T) ^ (Key1.S - Key1.T)) * Sgn((Key2.T - Key1.T) ^ (Key1.S - Key1.T)) <= 0 &&
        Sgn((Key1.S - Key2.T) ^ (Key2.S - Key2.T)) * Sgn((Key1.T - Key2.T) ^ (Key2.S - Key2.T)) <= 0;
}

int N;
Segment Segs[maxn];
Point Dot;
Ray Judge;

bool IsPointOnPolygon() {
    for (int i = 1; i <= N; ++i)
        if (IsPointOnSeg(Dot, Segs[i])) return true;
    return false;
}

bool IsPointInPolygon() {
    int Cnt = 0;
    for (int i = 1; i <= N; ++i) {
        if (Cmp(Segs[i].S.Y, Segs[i].T.Y) == 0) continue;
        if (IsSegInterSeg(Judge, Segs[i]) && Cmp(Segs[i].T.Y, Dot.Y)) {
            Cnt++;
        }
    }
    return Cnt & 1;
}

int main(int argc, char *argv[]) {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%lf%lf%lf%lf", &Segs[i].S.X, &Segs[i].S.Y, &Segs[i].T.X, &Segs[i].T.Y);
        if (Cmp(Segs[i].S.Y, Segs[i].T.Y) > 0) swap(Segs[i].S, Segs[i].T);
    }
    scanf("%lf%lf", &Dot.X, &Dot.Y);
    Judge = (Ray){Dot, (Point){inf, Dot.Y}};
    if (IsPointOnPolygon()) printf("BORDER\n");
    else if (IsPointInPolygon()) printf("INSIDE\n");
    else printf("OUTSIDE\n");
    return 0;
}