hexo-blog/source/_posts/oi/broken-line.md

---

title: Broken Line tags:

• Plane Geometry id: "1569" categories:
• - OI
  • Computational Geometry date: 2017-10-23 13:10:43 ---

题目描述

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 $(X_0, Y_0)$ is inside this closed broken line, outside or belongs to the broken line.

题意概述

给定一个简单$N$边形，它的每条边都平行于坐标轴。问点$(X_0, Y_0)$是否在多边形内。

数据范围：$4 \le N \le 10000$。

算法分析

从$(X_0, Y_0)$向右水平射出一条射线，若射线与$N$边形有奇数个交点则该点在多边形内。

判断一条边是否与射线相交就是要看该边的两个端点是否在射线异侧，在射线上或射线上方算同一侧，在射线下方算另一侧。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
  template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
  inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
  inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
  template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
  template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
  inline void write(char c) { putchar(c); }
  inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
  template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Line { int x1, y1, x2, y2; };

struct Solver {
private:
  static const int K = 10010;
  int k, x, y;
  Line l[K];
  void input() {
    io > k;
    for (int i = 1; i <= k; ++ i) {
      io > l[i].x1 > l[i].y1 > l[i].x2 > l[i].y2;
      if (l[i].x1 > l[i].x2 || l[i].y1 > l[i].y2) swap(l[i].x1, l[i].x2), swap(l[i].y1, l[i].y2);
    }
    io > x > y;
  }
  bool in(int x, int y, Line l) {
    if (l.x1 == l.x2) return x == l.x1 && l.y1 <= y && y <= l.y2;
    else return y == l.y1 && l.x1 <= x && x <= l.x2;
  }
  void process() {
    for (int i = 1; i <= k; ++ i) if (in(x, y, l[i])) { io < (char *) "BORDER\n"; return; }
    int cnt = 0;
    for (int i = 1; i <= k; ++ i)
      cnt += l[i].x1 == l[i].x2 && l[i].x1 > x && ((l[i].y1 <= y) ^ (l[i].y2 <= y));
    if (cnt & 1) io < (char *) "INSIDE\n"; else io < (char *) "OUTSIDE\n";
  }

public:
  void solve() { input(), process(); }
} solver;

int main() {
  solver.solve();
  return 0;
}