Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Lines

Category: JOI Tag: geometry

Lines

問題概要


直線のリストが与えられるので, それらの直線によって分割された平面の数を求めよ.

解法


平面グラフにおいて, 面の数fは頂点数vと辺数eと以下の関係をもつ

各直線から作られる辺の数は各直線が持つ交点数+1に等しいのでこれを求める.
頂点数は交点数.

コード


(Lines.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>

namespace D2
{
const double eps = 1e-8;

struct point
{
        double x, y;
        point():x(0),y(0){}
        point(double x, double y):x(x),y(y){}

        point operator+=(const point &p){ x+=p.x; y+=p.y; return *this;}
        point operator-=(const point &p){ x-=p.x; y-=p.y; return *this;}
        point operator*=(const double &d){ x*=d; y*=d; return *this;}
        point operator/=(const double &d){ x/=d; y/=d; return *this;}
        point operator+(const point &p)const{ return point(*this)+=p;}
        point operator-(const point &p)const{ return point(*this)-=p;}
        point operator*(const double &d)const{ return point(*this)*=d;}
        point operator/(const double &d)const{ return point(*this)/=d;}
        point operator-()const{ return point(-x,-y);}
        bool operator<(const point &p) const { return std::abs(x- p.x)>eps ? x < p.x-eps : y < p.y-eps;}
        bool operator==(const point &p) const { return std::abs(x-p.x)<eps and std::abs(y-p.y)<eps;}
        bool operator!=(const point &p) const { return !(point(*this)==p);}

        double norm() const { return x*x+y*y;}
        double abs() const { return sqrt(norm());}
        double det(const point &p) const { return x*p.y-y*p.x;}
};

struct line
{
        point a, b;
        line(){}
        line(point a, point b):a(a),b(b){}

        point vec() const { return b-a;}
};

inline bool ill(const line &l, const line &m){ return abs(l.vec().det(m.vec())) > eps;}
inline point cll(const line &l, const line &m){ return l.a+l.vec()*(m.vec().det(m.a-l.a)/m.vec().det(l.vec()));}

}

using namespace std;
using namespace D2;

int n, m, f[1024];
vector<point> V, W;
vector<line> E, F;

bool same(const line &l, const line &m){
        return abs(l.vec().det(m.vec())) < eps and abs(l.vec().det(m.a-l.a)) < eps;
}

int solve()
{

        for (int i = 0; i < n; i++) {
                if(!f[i]) E.push_back(F[i]);
                for (int j = i+1; j < n; j++)
                        if(!f[j] and same(F[i], F[j])) f[j] = 1;
        }

        m = E.size();
        int e = m;
        for(auto &a: E) {
                W.clear();
                for(auto &b: E) {
                        if(!ill(a,b)) continue;
                        point p = cll(a,b);
                        V.push_back(p);
                        W.push_back(p);
                }
                sort(begin(W),end(W));
                e += unique(begin(W),end(W))-begin(W);
        }
        sort(begin(V),end(V));
        int v = unique(begin(V),end(V))-begin(V);
        return 1-v+e;
}

void input()
{
        cin >> n;
        int a, b, c, d;
        for (int i = 0; i < n; i++) {
                cin >> a >> b >> c >> d;
                F.push_back(line(point(a,b),point(c,d)));
        }

}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments