//回憶系列:
//可以優化的，去除重復點，我這沒這一步，而且我比較懶，直接把離散這一步省略了，直接替代了
//不過離散化+線段樹思想是不變的,注釋比較少
1
//segment tree template
2#include <iostream>
3#include <algorithm>
4
5using namespace std;
6
struct Eage
{
7
long long xi;
8 long long yu,yd;
9 int flag;
10
bool operator<(const Eage& e)const{
11 return xi<e.xi;
12
};
13
}line[80210];
14long long dy[80210];
15
16struct Tnode{
17 //point left,right child
18 Tnode *lc,*rc;
19 //segment devide
20 int left,right;
21
22 //extra
23 int cnt;//是否覆蓋
24 long long len;//測度
25 long long yu,yd;
26 //construct function
27 Tnode(int data=0,int l=0,int r=0,Tnode*lp=0,Tnode*rp=0)
28 :left(l),right(r),lc(lp),rc(rp){
29 len=yu=yd=0.0;
30 cnt=0;
31 };
32};
33
34//maxsize number of Tnode
35const int N=80002;
36
37//static allocate memory for Tnode [a,b] node_size=2*(b-a)+1 for [i,i+1]
38Tnode node[N<<1];
39//count for usage Tnode array
40int cnt=0;
41
42//make a new node ,return Tnode*
43Tnode* new_node(){
44 Tnode* p=&node[cnt++];
45 memset(p,0,sizeof(Tnode));
46 return p;
47}
48
49//make tree ,return Tnode* which is root
50//parament: [left,right]
51Tnode* make_tree(int left,int right){
52 //make a new Tnode
53 Tnode* root=new_node();
54 //Initial the Tndoe
55 root->left=left,root->right=right;
56
57 if(left+1==right){
58 root->yu=dy[right];
59 root->yd=dy[left];
60 return root;
61 }else{
62 int mid=(left+right)>>1;
63 root->lc=make_tree(left,mid);
64 root->rc=make_tree(mid,right);
65 return root;
66 }
67}
68long long CalLen(Tnode* root){
69 root->len=0;
70 if(root->cnt>0){
71 root->len=dy[root->right] - dy[root->left];
72 return root->len;
73 }
74 if(root->lc)root->len=root->lc->len;
75 if(root->rc)root->len+=root->rc->len;
76
77 return root->len;
78};
79void Update(Tnode* root,Eage data){
80 if(dy[root->left]>=data.yd&&dy[root->right]<=data.yu){
81 root->cnt+=data.flag;
82 CalLen(root);
83 return ;
84 }
85 int mid=(root->left+root->right)>>1;
86 if(dy[mid]>=data.yu){
87 Update(root->lc,data);
88 }else if(dy[mid]<=data.yd){
89 Update(root->rc,data);
90 }else{
91 Eage tmp=data;
92 tmp.yu=dy[mid];
93 Update(root->lc,tmp);
94
95 tmp=data;
96 tmp.yd=dy[mid];
97 Update(root->rc,tmp);
98 }
99 CalLen(root);
100 return ;
101}
102int main()
103{
104 int e=1;
105 int n;
106 while(cin>>n){
107 cnt=0;
108 long long x1,y1,x2,y2;
109 for(int i=1;i<=2*n;i+=2){
110 cin>>x1>>x2>>y2;
111 y1=0;
112 line[i].xi=x1,line[i].yd=y1,line[i].yu=y2,line[i].flag=1;
113 line[i+1].xi=x2,line[i+1].yd=y1,line[i+1].yu=y2,line[i+1].flag=-1;
114 dy[i]=y1;
115 dy[i+1]=y2;
116 }
117 sort(line+1,line+2*n+1);
118 sort(dy+1,dy+2*n+1);
119 Tnode *root=make_tree(1,2*n);
120
121 long long area=0;
122 Update(root,line[1]);
123 for(int i=2;i<=2*n;i++){
124 area+=root->len*(line[i].xi-line[i-1].xi);
125 Update(root,line[i]);
126 }
127 //printf("Test case #%d\n",e++);
128 printf("%lld\n",area);
129 }
130 return 0;
131}
..
http://acm.pku.edu.cn/JudgeOnline/problem?id=3277
posted on 2009-03-09 14:27
小果子 閱讀(1210)
評論(0) 編輯 收藏 引用 所屬分類:
Acm