裸半平面交，以前没写过，先写一遍再说
我越来越不注意细节了，最后才发现空间稍微开小了（没有开那个零头，他又要多4条边，就WA了）
1 const 2 maxn=20010; 3 eps=1e-7; 4 type 5 point=record 6 x,y:double; 7 end; 8 poly=record 9 x,y,w:point; 10 end; 11 12 var 13 a:array[0..maxn]of poly; 14 n:longint; 15 16 operator -(a,b:point)c:point; 17 begin 18 c.x:=a.x-b.x; 19 c.y:=a.y-b.y; 20 end; 21 22 operator +(a,b:point)c:point; 23 begin 24 c.x:=a.x+b.x; 25 c.y:=a.y+b.y; 26 end; 27 28 operator *(a:point;b:double)c:point; 29 begin 30 c.x:=a.x*b; 31 c.y:=a.y*b; 32 end; 33 34 operator *(a,b:point)c:double; 35 begin 36 c:=a.x*b.y-a.y*b.x; 37 end; 38 39 function wh(a:point):longint; 40 begin 41 with a do 42 begin 43 if abs(x)<eps then 44 if y>eps then exit(2) 45 else exit(4) 46 else 47 if abs(y)<eps then 48 if x>eps then exit(1) 49 else exit(3) 50 else 51 if x>eps then 52 if y>eps then exit(1) 53 else exit(4) 54 else 55 if y>eps then exit(2) 56 else exit(3); 57 end; 58 end; 59 60 procedure swap(var x,y:poly); 61 var 62 t:poly; 63 begin 64 t:=x;x:=y;y:=t; 65 end; 66 67 procedure sort(l,r:longint); 68 var 69 i,j:longint; 70 y:point; 71 begin 72 i:=l; 73 j:=r; 74 y:=a[(l+r)>>1].w; 75 repeat 76 while (wh(a[i].w)<wh(y)) or ((wh(a[i].w)=wh(y)) and (y*a[i].w+eps<0)) do 77 inc(i); 78 while (wh(a[j].w)>wh(y)) or ((wh(a[j].w)=wh(y)) and (y*a[j].w>eps)) do 79 dec(j); 80 if i<=j then 81 begin 82 swap(a[i],a[j]); 83 inc(i); 84 dec(j); 85 end; 86 until i>j; 87 if i<r then sort(i,r); 88 if j>l then sort(l,j); 89 end; 90 91 procedure init; 92 var 93 i:longint; 94 begin 95 read(n); 96 for i:=1 to n do 97 with a[i] do 98 begin 99 read(x.x,x.y,y.x,y.y); 100 w:=y-x; 101 end; 102 a[n+2].x.x:=10000; 103 a[n+3].x.x:=10000; 104 a[n+3].x.y:=10000; 105 a[n+4].x.y:=10000; 106 for i:=0 to 3 do 107 begin 108 a[n+i+1].y:=a[n+((i+1)mod 4)+1].x; 109 a[n+i+1].w:=a[n+i+1].y-a[n+i+1].x; 110 end; 111 inc(n,4); 112 sort(1,n); 113 end; 114 115 function get(a,b:poly):point; 116 var 117 s1,s2:double; 118 begin 119 s1:=a.w*(b.y-a.x); 120 s2:=a.w*(b.x-a.x); 121 if s1*s2>eps then s1:=-s1 122 else 123 begin 124 s1:=abs(s1); 125 s2:=abs(s2); 126 end; 127 if abs(s1+s2)<eps then get:=b.x 128 else get:=b.x+(b.w*(s2/(s1+s2))); 129 end; 130 131 var 132 q:array[0..maxn]of poly; 133 d:array[0..maxn]of point; 134 l,r:longint; 135 ans:double; 136 137 procedure work; 138 var 139 i:longint; 140 begin 141 l:=1; 142 r:=1; 143 q[1]:=a[1]; 144 for i:=2 to n do 145 begin 146 while (l<r) and (a[i].w*(d[r-1]-a[i].x)+eps<0) do 147 dec(r); 148 while (l<r) and (a[i].w*(d[l]-a[i].x)+eps<0) do 149 inc(l); 150 inc(r); 151 q[r]:=a[i]; 152 if abs(q[r-1].w*q[r].w)<eps then 153 begin 154 dec(r); 155 if a[i].w*(q[r].x-a[i].x)<0 then q[r]:=a[i]; 156 end; 157 d[r-1]:=get(q[r],q[r-1]); 158 end; 159 while (l<r) and (q[l].w*(d[r-1]-q[l].x)+eps<0) do 160 dec(r); 161 if l<r then d[r]:=get(q[l],q[r]); 162 if r-l<=1 then writeln('0.0') 163 else 164 begin 165 for i:=l to r-1 do 166 ans:=ans+(d[i]*d[i+1])/2; 167 ans:=ans+(d[r]*d[l])/2; 168 ans:=abs(ans); 169 if ans<eps then writeln('0.0') 170 else writeln(ans:0:1); 171 end; 172 end; 173 174 begin 175 init; 176 work; 177 end.