ABC 016 D

今回はこの問題です。

abc016.contest.atcoder.jp

多角形の各頂点と、線分の２端点があたえられます。線分で多角形を切断した時、多角形はいくつに分割されるでしょう、という問題です。

(多角形の辺と直線の交点 / 2) + 1が答えとなります。
辺と直線の交点というか、この問題は交わっているか否かだけが必要となってくるのですが、それを求めるために外積を利用します。
この辺りは
平面幾何におけるベクトル演算 » 直線と線分
を参考にしました。
符号つき面積とか懐かしくてすっかり忘れてました。
回答は以下のようになりました。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    long long int gaiseki(int x1, int y1, int x2, int y2)
    {
        return x1 * y2 - x2 * y1;
    }
     
    bool iscross(int v1sx, int v1sy, int v1ex, int v1ey, int v2sx, int v2sy, int v2ex, int v2ey)
    {
        bool tmp1 = gaiseki(v1ex - v1sx, v1ey - v1sy, v2sx - v1sx, v2sy - v1sy) * gaiseki(v1ex - v1sx, v1ey - v1sy, v2ex - v1sx, v2ey - v1sy) < 0;
        bool tmp2 = gaiseki(v2ex - v2sx, v2ey - v2sy, v1sx - v2sx, v1sy - v2sy) * gaiseki(v2ex - v2sx, v2ey - v2sy, v1ex - v2sx, v1ey - v2sy) < 0;
        return tmp1 && tmp2;
    }
     
    int main()
    {
        int ax, ay, bx, by, n;
        cin >> ax >> ay >> bx >> by >> n;
        int x[101], y[101];
        cin >> x[0] >> y[0];
        int ans = 0;
        for(int i = 1; i < n; i++){
            cin >> x[i] >> y[i];
            if(iscross(ax, ay, bx, by, x[i - 1], y[i - 1], x[i], y[i])) ans++;
        }
        if(iscross(ax, ay, bx, by, x[n - 1], y[n - 1], x[0], y[0])) ans++;
        cout << ans / 2 + 1 << endl;
        return 0;
    }