AtCoder ABC 016 D - 一刀両断 (試験管水色)

幾何の問題。特に「線分と線分の交差判定」に関する問題！

• 問題へのリンク

問題概要

凸とは限らない 角形 が与えられる。 番目の頂点の座標は である。

この多角形 の外部に 2 点 , がある。この 2 点を結ぶことによって、多角形 をいくつかのピースに分ける。いくつのピースに分かれるかを求めよ。

制約

• 
• 
• 線分が多角形の頂点を通ることはない ( 以上離れている)

考えたこと

次の図は入力例 2 のものである。

見て取れるのは、線分と多角形の交点 (かならず偶数) が 2 増えるたびに、ピースが 1 個増えるということだ。

よって答えは、交点の数を として、 となる。計算量は である。

なお、問題を解くために必要なライブラリとしては「線分と線分が交差するかを判定する」処理ができればよい。幾何系統のライブラリを揃えるためには、螺旋本がオススメ！

コード

#include <bits/stdc++.h>
using namespace std;


/*/////////////////////////////*/
// 基本要素 (点, 線分, 円)
/*/////////////////////////////*/

using DD = double;
const DD INF = 1LL<<60;      // to be set appropriately
const DD EPS = 1e-10;        // to be set appropriately
const DD PI = acosl(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

/* Point */
struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

/* Line */
struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};


/*/////////////////////////////*/
// 円や直線の交差判定, 距離
/*/////////////////////////////*/

int ccw_for_dis(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > EPS) return 1;
    if (cross(b-a, c-a) < -EPS) return -1;
    if (dot(b-a, c-a) < -EPS) return 2;
    if (norm(b-a) < norm(c-a) - EPS) return -2;
    return 0;
}
Point proj(const Point &p, const Line &l) {
    DD t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
    return l[0] + (l[1] - l[0]) * t;
}
Point refl(const Point &p, const Line &l) {
    return p + (proj(p, l) - p) * 2;
}
bool isinterPL(const Point &p, const Line &l) {
    return (abs(p - proj(p, l)) < EPS);
}
bool isinterPS(const Point &p, const Line &s) {
    return (ccw_for_dis(s[0], s[1], p) == 0);
}
bool isinterLL(const Line &l, const Line &m) {
    return (abs(cross(l[1] - l[0], m[1] - m[0])) > EPS ||
            abs(cross(l[1] - l[0], m[0] - l[0])) < EPS);
}
bool isinterSS(const Line &s, const Line &t) {
    if (eq(s[0], s[1])) return isinterPS(s[0], t);
    if (eq(t[0], t[1])) return isinterPS(t[0], s);
    return (ccw_for_dis(s[0], s[1], t[0]) * ccw_for_dis(s[0], s[1], t[1]) <= 0 &&
            ccw_for_dis(t[0], t[1], s[0]) * ccw_for_dis(t[0], t[1], s[1]) <= 0);
}


/*/////////////////////////////*/
// solvers
/*/////////////////////////////*/

int main() {
    Point A, B;
    cin >> A.x >> A.y >> B.x >> B.y;
    int N;
    cin >> N;
    vector<Point> pol(N);
    for (int i = 0; i < N; ++i) cin >> pol[i].x >> pol[i].y;
    
    int num = 0;
    for (int i = 0; i < N; ++i) {
        Line ab(A, B);
        Line s(pol[i], pol[(i+1)%N]);
        if (isinterSS(ab, s)) ++num;
    }
    cout << num/2 + 1 << endl;
}