平面上有若幹個矩形，求矩形相互覆蓋的面積。為方便起見，矩形的邊均平行於坐標軸。 我們根據容斥原理，矩形相互覆蓋的面積即為所有矩形的面積和減去所有矩形所覆蓋的面積即可。 而現在問題是如何求得所有矩形所覆蓋的面積。即 讓我們人類去做，由於這是個由矩形拼接成的多邊形，很難去直接求它的面積，求該圖形的面積一 ...
平面上有若幹個矩形，求矩形相互覆蓋的面積。為方便起見，矩形的邊均平行於坐標軸。
我們根據容斥原理，矩形相互覆蓋的面積即為所有矩形的面積和減去所有矩形所覆蓋的面積即可。
而現在問題是如何求得所有矩形所覆蓋的面積。即
讓我們人類去做，由於這是個由矩形拼接成的多邊形，很難去直接求它的面積，求該圖形的面積一個常規的方法就是割補法。
此處我們採用割，割成一個一個矩形出來。
這樣就很方便地去求了。
電腦無法直觀地看出圖形，進而去求出長寬進而求出矩形面積。
那該如何讓電腦來求？
我們看這些圖形，一塊一塊的，最下麵的一塊，可以想象成原矩形
下麵矩形最下麵的邊，向上平移時“刷”出來的紫矩形，當碰到上面矩形的底邊時，兩條邊合併，再向上平移時“刷”出紅色矩形，然後碰到下麵矩形的頂邊，去掉了頂邊對應的底邊，因為兩邊重合的部分有兩條邊貢獻，所以去掉頂邊線段後，重合部分還在，繼續向上平移，“刷”出了藍色矩形。
有序，易行，電腦可做！
其實這就是掃描線在乾的事，一條透明的線從下向上平移，遇到底邊，則掃描線在底邊所在的範圍有了顏色，這樣向上平移的時候就“刷”出了顏色，遇到頂邊，則掃描線在頂邊的範圍就沒了顏色，之後該部分就沒有顏色了。
所以現在的問題是，如何維護掃描線。
即我們要維護，掃描線有底邊貢獻的範圍，以及該範圍被幾條底邊所貢獻，且當遇到頂邊時要把相應底邊的貢獻去掉。
很顯然，當底邊兩端點的坐標為實數，或者坐標範圍很大時，直接維護點坐標是不現實的。
實數怎麼辦？範圍很大怎麼辦？
離散呀！
我們註意到，所有矩形頂點的橫坐標，其實是把x軸分成了若幹個區間。
而任意一個矩形的底邊，只是會覆蓋若幹個區間，而不會只覆蓋某區間的一部分。
那我們就可以維護區間，從而避開了實數的無窮個數和範圍大造成數據冗餘以及記憶體爆表的問題。
當我們遇到一個矩形的底邊時，只需在底邊所覆蓋的若幹個區間加一，即貢獻一個底邊。
而在遇到一個矩形的頂邊的時候，在頂邊所覆蓋的若幹個區間減一，即去除該矩形底邊的貢獻。
最終，只要有底邊有貢獻的區間，都是掃描線“有顏色”的範圍。
這裡涉及到了區間加，區間減以及區間查詢。
拿什麼維護呢。
當然是線段樹啦。
所以，
根據邊的x坐標劃分離散x軸的區間，
拿線段樹去維護區間，
把邊按y軸從小到大排序，自1到n即自下而上掃描，
不斷更新掃描線的有顏色的範圍長度，再乘以上下兩邊的y軸的數值差，即為此部分掃描的面積。
重覆即可。
離散的寫法有好多，這裡運用STLl較為簡便的寫法。
註意離散後也要能映射回去。
Description
There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.Input
The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.The input file is terminated by a line containing a single 0. Don't process it.
Output
For each test case, your program should output one section. The first line of each section must be "Test case #k", where k is the number of the test case (starting with 1). The second one must be "Total explored area: a", where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.Output a blank line after each test case. 大意就是求島的面積（還是矩形的），給出若幹個矩形，以左上和右下點的坐標來表示，矩形間會有重疊，重疊部分只算一次。 掃一下就好了。 註意原題的一句話 Output a blank line after each test case. 否則你會Presentation Error
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <iostream> 6 #include <cmath> 7 #include <ctime> 8 #include <queue> 9 #define N 200 10 using namespace std; 11 struct seg{ //邊 12 double l,r,h; 13 int d; 14 seg(){} 15 seg(double xx,double yy,double hh,int dd):l(xx),r(yy),h(hh),d(dd){} //初始化函數 16 bool operator < (const seg &a) const{ //重載運算符，使其能夠進行快排 17 return (h<a.h); 18 } 19 }s[N*2]; 20 struct tree{ //線段樹 21 int mark; //mark記錄底邊對區間的貢獻 22 double sum; //sum記錄底邊貢獻的範圍 23 }t[N*10]; 24 int n,ll,rr,num,size,qwq; //qwq 25 double ans,rank[N*10]; //rank做離散用 26 void readint(int &x){ 27 x=0; 28 char c; 29 int w=1; 30 for (c=getchar();c<'0'||c>'9';c=getchar()) 31 if (c=='-') w=-1; 32 for (;c>='0'&&c<='9';c=getchar()) 33 x=(x<<3)+(x<<1)+(c^'0'); 34 x*=w; 35 } 36 void readlong(long long &x){ 37 x=0; 38 char c; 39 long long w=1; 40 for (c=getchar();c<'0'||c>'9';c=getchar()) 41 if (c=='-') w=-1; 42 for (;c>='0'&&c<='9';c=getchar()) 43 x=(x<<3)+(x<<1)+(c^'0'); 44 x*=w; 45 } 46 void pushup(int root,int ll,int rr){ 47 if (t[root].mark) t[root].sum=rank[rr+1]-rank[ll]; //離散後的數字映射回原來的數字 48 else if (ll==rr) t[root].sum=0; 49 else t[root].sum=t[root<<1].sum+t[root<<1|1].sum; 50 } 51 void updata(int l,int r,int d,int root,int ll,int rr){ 52 if (l<=ll&&rr<=r){ 53 t[root].mark+=d; 54 pushup(root,ll,rr); 55 return; 56 } 57 int mid=(ll+rr)>>1; 58 if (l<=mid) updata(l,r,d,root<<1,ll,mid); 59 if (r>mid) updata(l,r,d,root<<1|1,mid+1,rr); 60 pushup(root,ll,rr); 61 } 62 int main(){ 63 qwq=0; 64 while (true){ 65 ++qwq; //qwq只是情況記錄的個數qwq 66 num=0; 67 ans=0; 68 readint(n); 69 if (n==0) return 0; //應題目要求 70 for (int i=1;i<=n;++i){ 71 double x1,y1,x2,y2; 72 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 73 s[++num]=seg(x1,x2,y2,1); 74 rank[num]=x1; 75 s[++num]=seg(x1,x2,y1,-1); 76 rank[num]=x2; 77 } 78 sort(rank+1,rank+1+num); 79 sort(s+1,s+1+num); 80 size=unique(rank+1,rank+1+num)-(rank+1); //去重,size為去重後點的個數，為離散做準備 81 s[num+1].h=s[num].h; //小細節，只為下麵i迴圈後mark能清零且不會在i=n時對結果造成影響 82 for (int i=1;i<=num;++i){ 83 ll=lower_bound(rank+1,rank+1+size,s[i].l)-(rank+1)+1; //這裡左邊第一個點標號為1，其點右邊第一個區間標號也為1 84 rr=lower_bound(rank+1,rank+1+size,s[i].r)-(rank+1); //離散，ll,rr為邊覆蓋的最左區間和最右區間的標號 85 updata(ll,rr,s[i].d,1,1,size-1); //植樹原理，一條直線，兩頭植樹，n個點，n-1個區間 86 ans+=t[1].sum*(s[i+1].h-s[i].h); //長乘寬 87 } 88 printf("Test case #%d\nTotal explored area: %.2f\n\n",qwq,ans); 89 } 90 return 0; 91 }神奇的代碼
什麼？你說4+2第一天那道絕地求生，有若幹個圓形輻射區，問安全區的面積怎麼用掃描線掃？
那聽說是道圓的面積並的模板題，但本蒟蒻還不會……
