平面グラフの面の個数を考える系問題

問題概要

二次元平面上に $N$ 本の直線が与えられる。これらの直線は、それらを通る 2 点の座標 ( $(a_{i}, b_{i})$ と $(c_{i}, d_{i})$ を通る) で与えられる。

これらの直線によって、平面全体が何個の領域に分割されるのかを求めよ。

制約

$1 \le N \le 1000$
$0 \le a_{i}, b_{i}, c_{i}, d_{i} \le 1000$

考えたこと

Euler の定理を使ってもよいし、もっとアドホックな考察でも解ける。まず Euler の定理とは、

平面グラフの頂点数を $V$ 、辺数を $E$ 、面数を $F$ としたとき
$V - E + F = 2$ が成立する

というもの。これを知っていれば、頂点数 (交点数) と辺数を計算すれば解ける。

kagamiz.hatenablog.com

一方、簡単な考察でも解ける。すでに $k$ 本の直線が引かれているとき、新たに 1 本の線を引くことによって、平面領域が何個増加するかを考えよう。新たな直線が既存の直線と $m$ 箇所で交わるとする ( $m \lt k$ になりうる)。このとき、増加する平面領域の個数は $m+1$ となる。

はじめに直線がまったくない状態 (平面が 1 個だけ) からスタートして、1 本ずつ直線を引いていき、その度に増加する平面両機の個数を足していけば OK。

コード

直線を追加するたびに、既存の直線との交点を求め、さらにそれらが何種類に潰れるのかを求める (ソートを使うなど) ことから、計算量は $O(N^{2} \log N)$ となる。

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

// 幾何ライブラリ
using DD = double;   // 誤差が厳しかったら、ここを long double に変更
const DD EPS = 1e-8; // to be set appropriately

/* 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 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 abs(const Point &p) {return sqrt(dot(p, p));}
inline bool issame(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);}

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] << '}';}
};

// 直線の交点
vector<Point> crosspoint(const Line &l, const Line &m) {
    vector<Point> res;
    DD d = cross(m[1] - m[0], l[1] - l[0]);
    if (abs(d) < EPS) return vector<Point>();
    res.push_back(l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) / d);
    return res;
}

// 直線が一致するかどうか
bool issame(const Line &l, const Line &m) {
    if (abs(cross(m[0] - l[0], l[1] - l[0])) > EPS) return false;
    if (abs(cross(m[1] - l[0], l[1] - l[0])) > EPS) return false;
    return true;
}


int main() {
    int N;
    cin >> N;
    vector<Point> S(N), T(N);
    for (int i = 0; i < N; ++i) cin >> S[i].x >> S[i].y >> T[i].x >> T[i].y;
    vector<Line> L;
    for (int i = 0; i < N; ++i) {
        Line l(S[i], T[i]);
        bool isnew = true;
        for (auto pl : L) if (issame(l, pl)) isnew = false;
        if (isnew) L.push_back(l);
    }
 
    int res = 1;
    for (int i = 0; i < L.size(); ++i) {
        vector<Point> vp;
        for (int j = 0; j < i; ++j) {
            auto cr = crosspoint(L[i], L[j]);
            for (auto p : cr) vp.push_back(p);
        }
        sort(vp.begin(), vp.end());
        int add = 0;
        for (int i = 0; i < vp.size(); ++i) {
            if (i > 0 && issame(vp[i], vp[i-1])) continue;
            ++add;
        }
        res += add + 1;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 春合宿 2007 day4-2 Lines (難易度 9)

問題概要

制約

考えたこと

コード