POJ1474 Video Surveillance(半平面交)

很多道相似的半平面交，但隻過了這個，心都碎了。。

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

<code>#pragma warning(disable:4996)</code>

<code>#include &lt;iostream&gt;</code>

<code>#include &lt;cstring&gt;</code>

<code>#include &lt;cstdio&gt;</code>

<code>#include &lt;vector&gt;</code>

<code>#include &lt;cmath&gt;</code>

<code>#include &lt;string&gt;</code>

<code>#include &lt;algorithm&gt;</code>

<code>using</code>

<code>namespace</code> <code>std;</code>

<code>#define maxn 2500</code>

<code>#define eps 1e-7</code>

<code>int</code>

<code>n;</code>

<code>dcmp(</code><code>double</code>

<code>x){</code>

<code>    </code><code>return</code>

<code>x&lt;-eps ? -1 : x&gt;eps;</code>

<code>}</code>

<code>struct</code>

<code>point</code>

<code>{</code>

<code>    </code><code>double</code>

<code>x, y;</code>

<code>    </code><code>point(){}</code>

<code>    </code><code>point(</code><code>double</code>

<code>_x,</code><code>double</code>

<code>_y) :x(_x), y(_y){}</code>

<code>    </code><code>point operator + (</code><code>const</code>

<code>point &amp;b)</code><code>const</code><code>{</code>

<code>        </code><code>return</code>

<code>point(x + b.x, y + b.y);</code>

<code>    </code><code>}</code>

<code>    </code><code>point operator - (</code><code>const</code>

<code>point(x - b.x, y - b.y);</code>

<code>    </code><code>point operator *(</code><code>double</code>

<code>d)</code><code>const</code><code>{</code>

<code>point(x*d, y*d);</code>

<code>    </code><code>point operator /(</code><code>double</code>

<code>point(x / d, y / d);</code>

<code>det(</code><code>const</code>

<code>x*b.y - y*b.x;</code>

<code>dot(</code><code>const</code>

<code>x*b.x + y*b.y;</code>

<code>    </code><code>point rot90(){</code>

<code>point(-y, x);</code>

<code>    </code><code>point norm(){</code>

<code>        </code><code>double</code>

<code>len =</code><code>sqrt</code><code>(</code><code>this</code><code>-&gt;dot(*</code><code>this</code><code>));</code>

<code>point(x, y) / len;</code>

<code>    </code><code>void</code>

<code>read(){</code>

<code>        </code><code>scanf</code><code>(</code><code>"%lf%lf"</code><code>, &amp;x, &amp;y);</code>

<code>};</code>

<code>#define cross(p1,p2,p3) ((p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y))</code>

<code>#define crossop(p1,p2,p3) (dcmp(cross(p1,p2,p3)))</code>

<code>point isss(point p1, point p2, point q1, point q2){</code>

<code>a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);</code>

<code>(p1*a2 + p2*a1) / (a1 + a2);</code>

<code>border</code>

<code>    </code><code>point p1, p2;</code>

<code>alpha;</code>

<code>setalpha(){</code>

<code>        </code><code>alpha =</code><code>atan2</code><code>(p2.y - p1.y, p2.x - p1.x);</code>

<code>bool</code>

<code>operator &lt; (</code><code>const</code>

<code>border &amp;a,</code><code>const</code>

<code>border &amp;b) {</code>

<code>    </code><code>int</code>

<code>c = dcmp(a.alpha - b.alpha);</code>

<code>    </code><code>if</code>

<code>(c != 0) {</code>

<code>c &gt; 0;</code>

<code>    </code><code>else</code>

<code>crossop(b.p1, b.p2, a.p1) &gt; 0;</code>

<code>operator == (</code><code>const</code>

<code>border &amp;b){</code>

<code>dcmp(a.alpha - b.alpha) == 0;</code>

<code>point isborder(</code><code>const</code>

<code>isss(a.p1, a.p2, b.p1, b.p2);</code>

<code>border border[maxn];</code>

<code>border que[maxn];</code>

<code>qh, qt;</code>

<code>// check函數判斷的是新加的半平面和由a,b兩個半平面産生的交點的方向，若在半平面的左側傳回true</code>

<code>check(</code><code>const</code>

<code>border &amp;b,</code><code>const</code>

<code>border &amp;me){</code>

<code>    </code><code>point is = isborder(a, b);</code>

<code>crossop(me.p1, me.p2, is) &gt;= 0;</code>

<code>isparellel(</code><code>const</code>

<code>dcmp((a.p2 - a.p1).det(b.p2 - b.p1)) == 0;</code>

<code>convexintersection()</code>

<code>    </code><code>qh = qt = 0;</code>

<code>    </code><code>sort(border, border + n);</code>

<code>    </code><code>n = unique(border, border + n) - border;</code>

<code>    </code><code>for</code>

<code>(</code><code>int</code> <code>i = 0; i &lt; n; i++){</code>

<code>        </code><code>border cur = border[i];</code>

<code>        </code><code>while</code>

<code>(qh + 1 &lt; qt&amp;&amp;!check(que[qt - 2], que[qt - 1], cur)) --qt;</code>

<code>(qh + 1 &lt; qt&amp;&amp;!check(que[qh], que[qh + 1], cur)) ++qh;</code>

<code>        </code><code>que[qt++] = cur;</code>

<code>    </code><code>while</code>

<code>(qh + 1 &lt; qt&amp;&amp;!check(que[qt - 2], que[qt - 1], que[qh])) --qt;</code>

<code>(qh + 1 &lt; qt&amp;&amp;!check(que[qh], que[qh + 1], que[qt - 1])) ++qh;</code>

<code>qt - qh &gt; 2;</code>

<code>point ps[maxn];</code>

<code>main()</code>

<code>ca = 0;</code>

<code>(cin &gt;&gt; n&amp;&amp;n)</code>

<code>    </code><code>{</code>

<code>        </code><code>for</code>

<code>            </code><code>ps[i].read();</code>

<code>        </code><code>}</code>

<code>        </code><code>ps[n] = ps[0];</code>

<code>            </code><code>border[i].p1 = ps[i + 1];</code>

<code>            </code><code>border[i].p2 = ps[i];</code>

<code>            </code><code>border[i].setalpha();</code>

<code>        </code><code>printf</code><code>(</code><code>"floor #%d\n"</code><code>, ++ca);</code>

<code>        </code><code>if</code>

<code>(convexintersection()) {</code>

<code>            </code><code>puts</code><code>(</code><code>"surveillance is possible."</code><code>);</code>

<code>        </code><code>else</code>

<code>puts</code><code>(</code><code>"surveillance is impossible."</code><code>);</code>

<code>        </code><code>puts</code><code>(</code><code>""</code><code>);</code>

<code>0;</code>