假设从起点开始一直沿Y轴向上走 看穿过了几条边
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstring>
#include<cmath>
#define fabs(x) ((x) < 0 ? (-(x)) : (x))
#define SF scanf
#define PF printf
using namespace std;
typedef long long LL;
const int MAXN = 100000;
const int INF = 1234567890;
const double L = 100000.0;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct Vector {
double x, y;
Vector () {}
Vector (double xx, double yy) { x = xx; y = yy; }
Vector (double rad) { x = cos(rad); y = sin(rad); }
double len() const { return sqrt(x*x + y*y); }
Vector operator + (const Vector &b) const {
return Vector(x + b.x, y + b.y);
}
Vector operator - (const Vector &b) const {
return Vector(x - b.x, y - b.y);
}
Vector operator * (const double &b) const {
return Vector(x * b, y * b);
}
Vector operator / (const double &b) const {
return Vector(x / b, y / b);
}
bool operator < (const Vector &b) const {
return (x < b.x || (x == b.x && y < b.y));
}
};
typedef Vector Point, Angle;
struct Line {
Point P;
Vector v;
double ang;
Line () {}
Line (Point A, Vector B) : P(A), v(B) { ang = atan2(v.y, v.x); }
bool operator < (const Line &L) const {
return ang < L.ang;
}
};
double Dot(const Vector &a, const Vector &b) {
return a.x * b.x + a.y * b.y;
}
double Cross(const Vector &a, const Vector &b) {
return a.x * b.y - a.y * b.x;
}
Vector GetAngle(const Vector &a, const Vector &b) {
double l1 = a.len(), l2 = b.len();
return Vector(Dot(a, b) / l1 / l2, Cross(a, b)/ l1 / l2);
}
Vector Rotate(const Vector &a, const Angle &angle) {
return Vector(a.x * angle.x - a.y * angle.y, a.x * angle.y + a.y * angle.x);
}
Point GetIntersection(const Point &a, const Point &b, const Point &c, const Point &d)
{
double t = 1.0 * Cross(d - c, a - c) / Cross(b - a, d - c);
return a + (b - a) * t;
}
Point GetIntersection(const Line &a, const Line &b)
{
Vector u = a.P - b.P;
double t = Cross(b.v, u) / Cross(a.v, b.v);
return a.P + a.v * t;
}
int GetDirection(const Point &a, const Point &b, const Point &c)
{
// -1 逆时针
Vector v = b - a, B = c - a;
double flag = Cross(B, v);
if(flag < 0) return -1; if(flag > 0) return 1; return 0;
}
double GetDis(Point &a, Point &b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool OnLeft(Line L, Point P) {
return Cross(L.v, P-L.P) > 0;
}
bool HalfPlaneIntersection(Line *L, int N, Point *Ans)
{
sort(L, L+N);
int F, R;
Point *p = new Point[N]; // p[i]为q[i+1]和q[i]的交点
Line *q = new Line[N]; // p左闭右开 q左闭右闭
q[F=R=0] = L[0];
for(int i = 1; i < N; i++) {
while(F < R && !OnLeft(L[i], p[R-1])) R--;
while(F < R && !OnLeft(L[i], p[F])) F++;
q[++R] = L[i];
if(fabs(Cross(q[R].v, q[R-1].v)) < EPS) {
R--;
if(OnLeft(q[R], L[i].P)) q[R] = L[i];
}
if(F < R) p[R-1] = GetIntersection(q[R-1], q[R]);
}
while(F < R && !OnLeft(q[F], p[R-1])) R--;
if(R - F < 2) return 0;
p[R] = GetIntersection(q[F], q[R]);
int CNT = 0;
for(int i = F; i <= R; i++) Ans[CNT++] = p[i];
return CNT;
}
int ConvexHull(Point *p, int N, Point *ch)
{
sort(p, p+N);
int R = 0;
for(int i = 0; i < N; i++) {
while(R > 1 && Cross(ch[R-1]-ch[R-2], p[i]-ch[R-2]) <= EPS) R--;
ch[R++] = p[i];
}
int F = R;
for(int i = N-2; i >= 0; i--) {
while(R > F && Cross(ch[R-1]-ch[R-2], p[i]-ch[R-2]) <= EPS) R--;
ch[R++] = p[i];
}
if(N > 1) R--;
return R;
}
bool PointInPolygon(Point *p, int N, Point x)
{
bool in = false;
for(int i = 2, j = i - 1; i <= N * 2; i += 2, j += 2 )
if((p[i].y > x.y) != (p[j].y > x.y) &&
x.x < (p[j].x - p[i].x) * (x.y - p[i].y) / (p[j].y - p[i].y) + p[i].x)
in = !in;
return in;
}
bool OnBorder(Point *A, int N, Point x)
{
for(int i = 1; i <= N * 2; i += 2)
{
if(((x.x < A[i].x) == (x.x > A[i+1].x)) && fabs(x.y - A[i].y) <= EPS && fabs(A[i+1].y - A[i].y) <= EPS) return true;
if(((x.y < A[i].y) == (x.y > A[i+1].y)) && fabs(x.x - A[i].x) <= EPS && fabs(A[i+1].x - A[i].x) <= EPS) return true;
if(((x.x < A[i].x) == (x.x > A[i+1].x)) && fabs(x.y - A[i].y + (A[i].x - x.x) / (A[i+1].x - A[i].x) * (A[i+1].y - A[i].y)) <= EPS) return true;
}
return false;
}
Point A[MAXN*2+10], st;
int main()
{
int n;
SF("%d", &n);
for(int i = 1; i <= n; i++) {
SF("%lf%lf", &A[i*2-1].x, &A[i*2-1].y);
SF("%lf%lf", &A[i*2].x, &A[i*2].y);
if(A[i*2].x < A[i*2-1].x) swap(A[i*2], A[i*2-1]);
if(A[i*2].y < A[i*2-1].y) swap(A[i*2], A[i*2-1]);
}
SF("%lf%lf", &st.x, &st.y);
if(OnBorder(A, n, st)) puts("BORDER");
else if(PointInPolygon(A, n, st)) puts("INSIDE");
else puts("OUTSIDE");
}