解題區/解題區 - Zerojudge

b325. 人格分裂

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 附錄 DC

Problem

某 M 現在正在平面座標上的原點 $(0, 0)$，現在四周被擺放了很多很多鏡子，某 M 可以藉由鏡子與他的人格小夥伴對話，請問那些鏡子可以見到小夥伴。

鏡子可以當作一個線段，線段之間不會交任何一點，只要能見到該鏡子中一小段區域就算可見到。

備註：不考慮反射看到，保證鏡子不會通過原點。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
5 -5 5 5
4
4 2 5 -2
2 4 6 1
5 5 8 1
3 -4 7 -1
7
-1 2 3 1
2 4 5 -1
-3 -1 1 -2
-1 -4 3 -2
-2 -4 1 -5
-4 1 -1 4
-3 4 -4 3
1
1 1 2 2
2
-1 3 -2 -2
-2 -1 -3 -1

Sample Output

1
2
3
4
5
1
1 1 0 1
1 1 1 1 0 1 0
0
1 0

Solution

對於每一個線段，可以化作極角座標上的一個角度區間$[\theta_{start}, \theta_{end}]$，做一次極角排序，維護從原點射出的射線，找到該射線交到的所有角度區間，意即維護射線和線段交的最近距離，用一個平衡樹 set<Seg> 維護。由於線段之間不會相交，平衡樹靠遠近當作權重比較，遠近關係是單調的，故不影響插入和刪除。若發生遠近問題可採用 multiset<Seg> 來進行。

由於每一個線段可能拆分好幾個可視線段，而大多數的線段全是不可視的，可以考慮分治去處理，但我的實作效果並不好，其原因在於並沒有維護極角的 skyline，而是保留整個線段。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-12
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double dist2(Pt a) {
    	return (x - a.x)*(x - a.x)+(y - a.y)*(y - a.y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt getIntersect(Pt as, Pt ae, Pt bs, Pt be) {
    Pt u = as - bs;
    double t = cross2(be - bs, u)/cross2(ae - as, be - bs);
    return as + (ae - as) * t;
}
struct Seg {
    Pt s, e;
    int id;
    Seg(Pt a = Pt(), Pt b = Pt(), int c = 0):
        s(a), e(b), id(c) {}
};
bool polar_cmp(const Pt& p1, const Pt& p2) {
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || (c == 0 && fabs(p1.x) < fabs(p2.x));
}
bool polar_cmp2(pair<Pt, int> x, pair<Pt, int> y) {
    return polar_cmp(x.first, y.first);
}
int cmpZero(double x) {
    if (fabs(x) < eps)	return 0;
    return x < 0 ? -1 : 1;
}
struct CMP {
    static Pt ray_s, ray_e;
    
    bool operator()(const Seg &x, const Seg &y) {
        Pt v1 = getIntersect(ray_s, ray_e, x.s, x.e);
        Pt v2 = getIntersect(ray_s, ray_e, y.s, y.e);
        return cmpZero(ray_s.dist2(v1) - ray_s.dist2(v2)) < 0;
    }
    static bool ray2seg(Seg x) {
        if (cmpZero(cross(ray_s, ray_e, x.s))*cmpZero(cross(ray_s, ray_e, x.e)) < 0) {
            return cmpZero(cross(x.s, ray_s, ray_s+ray_e))*cmpZero(cross(x.s, ray_s, x.e)) >= 0 &&
                    cmpZero(cross(x.e, ray_s, ray_s+ray_e))*cmpZero(cross(x.e, ray_s, x.s)) >= 0;
        }
        return false;
    }
};
Pt CMP::ray_s, CMP::ray_e;
const int MAXN = 32768;
int visual[MAXN];
Seg segs[MAXN];
int main() {
    int N, sx, sy, ex, ey;
    while (scanf("%d", &N) == 1) {
        vector< pair<Pt, int> > A;
        set<Seg, CMP> S;
        for (int i = 1; i <= N; i++) {
            scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
            A.push_back(make_pair(Pt(sx, sy), i));
            A.push_back(make_pair(Pt(ex, ey), -i));
            segs[i] = Seg(Pt(sx, sy), Pt(ex, ey), i);
            visual[i] = 0;
        }
        sort(A.begin(), A.end(), polar_cmp2);
        CMP::ray_s = Pt(0, 0), CMP::ray_e = A[0].first;
        
        for (int i = 1; i <= N; i++) {
            if (CMP::ray2seg(segs[i]))
                S.insert(segs[i]);
        }
        
        for (int i = 0; i < A.size(); ) {
            CMP::ray_e = A[i].first;
            while (i < A.size() && cmpZero(cross(CMP::ray_s, CMP::ray_e, A[i].first)) == 0) {
                int clockwise, id = abs(A[i].second);
                if (A[i].second > 0) 
                    clockwise = cmpZero(cross(CMP::ray_s, segs[id].s, segs[id].e));
                else 
                    clockwise = cmpZero(cross(CMP::ray_s, segs[id].e, segs[id].s));
                if (clockwise) {
                    if (clockwise > 0)
                        S.insert(segs[id]);
                    else
                        S.erase(segs[id]);
                }
                i++;
            }
            if (S.size() > 0) 
                visual[S.begin()->id] = 1;
        }
        for (int i = 1; i <= N; i++)
            printf("%d%c", visual[i], i == N ? '\n' : ' ');
    }
    return 0;
}

附錄 DC

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-9
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    x(a), y(b) {}
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    Pt operator*(const double a) const {
        return Pt(x * a, y * a);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
    double dist2(Pt a) {
    	return (x - a.x)*(x - a.x)+(y - a.y)*(y - a.y);
    }
};
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
Pt getIntersect(Pt as, Pt ae, Pt bs, Pt be) {
    Pt u = as - bs;
    double t = cross2(be - bs, u)/cross2(ae - as, be - bs);
    return as + (ae - as) * t;
}
struct Seg {
    Pt s, e;
    int id;
    Seg(Pt a = Pt(), Pt b = Pt(), int c = 0):
        s(a), e(b), id(c) {}
};
bool polar_cmp(const Pt& p1, const Pt& p2) {
    if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
    if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
    if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
    if (p1.y * p2.y < 0) return p1.y > p2.y;
    double c = cross2(p1, p2);
    return c > 0 || (c == 0 && fabs(p1.x) < fabs(p2.x));
}
bool polar_cmp2(pair<Pt, int> x, pair<Pt, int> y) {
    return polar_cmp(x.first, y.first);
}
int cmpZero(double x) {
    if (fabs(x) < eps)	return 0;
    return x < 0 ? -1 : 1;
}
struct CMP {
    static Pt ray_s, ray_e;
    
    bool operator()(const Seg &x, const Seg &y) {
        Pt v1 = getIntersect(ray_s, ray_e, x.s, x.e);
        Pt v2 = getIntersect(ray_s, ray_e, y.s, y.e);
        return cmpZero(ray_s.dist2(v1) - ray_s.dist2(v2)) < 0;
    }
    static bool ray2seg(Seg x) {
        if (cmpZero(cross(ray_s, ray_e, x.s))*cmpZero(cross(ray_s, ray_e, x.e)) < 0) {
            return cmpZero(cross(x.s, ray_s, ray_s+ray_e))*cmpZero(cross(x.s, ray_s, x.e)) >= 0 &&
                    cmpZero(cross(x.e, ray_s, ray_s+ray_e))*cmpZero(cross(x.e, ray_s, x.s)) >= 0;
        }
        return false;
    }
};
Pt CMP::ray_s, CMP::ray_e;
const int MAXN = 32768;
int visual[MAXN];
Seg mirror[MAXN], sm[MAXN];
vector<Seg> computePolar(vector<Seg> segs) {
    if (segs.size() == 0)
        return vector<Seg>();
    vector< pair<Pt, int> > A;
    set<Seg, CMP> S;
    for (int i = 0; i < segs.size(); i++) {
        A.push_back(make_pair(segs[i].s, segs[i].id));
        A.push_back(make_pair(segs[i].e, -segs[i].id));
        visual[segs[i].id] = 0;
    }
    sort(A.begin(), A.end(), polar_cmp2);
    CMP::ray_s = Pt(0, 0), CMP::ray_e = A[0].first;
    for (int i = 0; i < segs.size(); i++) {
        if (CMP::ray2seg(segs[i]))
            S.insert(segs[i]);
    }
    for (int i = 0; i < A.size(); ) {
        CMP::ray_e = A[i].first;
        while (i < A.size() && cmpZero(cross(CMP::ray_s, CMP::ray_e, A[i].first)) == 0) {
            int clockwise, id = abs(A[i].second);
            if (A[i].second > 0) 
                clockwise = cmpZero(cross(CMP::ray_s, sm[id].s, sm[id].e));
            else 
                clockwise = cmpZero(cross(CMP::ray_s, sm[id].e, sm[id].s));
            if (clockwise) {
                if (clockwise > 0)
                    S.insert(sm[id]);
                else
                    S.erase(sm[id]);
            }
            i++;
        }
        if (S.size() > 0) 
            visual[S.begin()->id] = 1;
    }
    vector<Seg> ret;
    for (int i = 0; i < segs.size(); i++) {
        if (visual[segs[i].id])
            ret.push_back(segs[i]);
    }
    return ret;
}
vector<Seg> dfs(int l, int r) {
    vector<Seg> L, R;
    if (l > r)	return L;
    if (l == r)
        return computePolar(vector<Seg>(mirror+l, mirror+l+1));
    int mid = (l+r)/2;
    L = dfs(l, mid);
    R = dfs(mid+1, r);
    L.insert(L.end(), R.begin(), R.end());
    return computePolar(L);
}
bool cmp(Seg a, Seg b) {
    return polar_cmp(a.s, b.s);
}
int main() {
    int N, sx, sy, ex, ey;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++) {
            scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
            Pt s(sx, sy), e(ex, ey);
            if (polar_cmp(s, e))
                swap(s, e);
            sm[i] = mirror[i] = Seg(s, e, i);
        }
        sort(mirror+1, mirror+N, cmp);
        dfs(1, N);
        for (int i = 1; i <= N; i++)
            printf("%d%c", visual[i], i == N ? '\n' : ' ');
    }
    return 0;
}