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.

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

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;
}
Last modification：March 27th, 2019 at 08:54 pm