扫描线三巨头hdu1928hdu1255hdu1542[POJ1151]

1 //#pragma comment(linker, "/STACK:1024000000,1024000000")
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define clr(x) memset(x,0,sizeof(x))
8 #define MAXN 50010
9 using namespace std;
10 struct edgx
11 {
12 int l,u,x;
13 int d;
14 }edgex[MAXN];
15 struct edgy
16 {
17 int l,r,y;
18 int d;
19 }edgey[MAXN];
20 struct seg
21 {
22 int l,r,cov,len;
23 }segt[MAXN<<2];
24 int cntx,cnty;
25 int x[MAXN],y[MAXN],vec[MAXN];
26 bool cmpy(edgy a,edgy b)
27 {
28 if(a.y&＃61;&＃61;b.y) return a.d>b.d;
29 return a.y<b.y;
30 }
31 bool cmpx(edgx a,edgx b)
32 {
33 if(a.x&＃61;&＃61;b.x) return a.d>b.d;
34 return a.x<b.x;
35 }
36 void init(int i,int l,int r)
37 {
38 segt[i]&＃61;(seg){l,r,0,0};
39 if(l&＃61;&＃61;r)
40 return ;
41 int mid&＃61;(l&＃43;r)>>1;
42 init(i<<1,l,mid);
43 init(i<<1|1,mid&＃43;1,r);
44 return ;
45 }
46 void pushup(int i)
47 {
48 if(segt[i].cov)
49 {
50 segt[i].len&＃61;vec[segt[i].r&＃43;1]-vec[segt[i].l];
51 }
52 else if(segt[i].l&＃61;&＃61;segt[i].r)
53 {
54 segt[i].len&＃61;0;
55 }
56 else
57 {
58 segt[i].len&＃61;segt[i<<1].len&＃43;segt[i<<1|1].len;
59 }
60 return ;
61 }
62 void update(int i,int l,int r,int value)
63 {
64 if(segt[i].l>&＃61;l && segt[i].r<&＃61;r)
65 {
66 segt[i].cov&＃43;&＃61;value;
67 pushup(i);
68 return ;
69 }
70 int mid&＃61;(segt[i].l&＃43;segt[i].r)>>1;
71 if(mid>&＃61;r)
72 {
73 update(i<<1,l,r,value);
74 }
75 else if(mid<l)
76 {
77 update(i<<1|1,l,r,value);
78 }
79 else
80 {
81 update(i<<1,l,r,value);
82 update(i<<1|1,l,r,value);
83 }
84 pushup(i);
85 return ;
86 }
87 int main()
88 {
89 int x1,x2,y1,y2,n,m,T,ans,l,r,k;
90 while(scanf("%d",&n)!&＃61;EOF)
91 {
92 cntx&＃61;0;
93 cnty&＃61;0;
94 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
95 {
96 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
97 edgex[&＃43;&＃43;cntx]&＃61;(edgx){y1,y2,x1,1};
98 x[cntx]&＃61;x1;
99 edgex[&＃43;&＃43;cntx]&＃61;(edgx){y1,y2,x2,-1};
100 x[cntx]&＃61;x2;
101 edgey[&＃43;&＃43;cnty]&＃61;(edgy){x1,x2,y1,1};
102 y[cnty]&＃61;y1;
103 edgey[&＃43;&＃43;cnty]&＃61;(edgy){x1,x2,y2,-1};
104 y[cnty]&＃61;y2;
105 }
106 n<<&＃61;1;
107 ans&＃61;0;
108 memcpy(vec,x,sizeof(x));
109 sort(vec&＃43;1,vec&＃43;n&＃43;1);
110 m&＃61;unique(vec&＃43;1,vec&＃43;n&＃43;1)-vec-1;
111 sort(edgey&＃43;1,edgey&＃43;n&＃43;1,cmpy);
112 init(1,1,m);
113 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
114 if(edgey[i].l<edgey[i].r)
115 {
116 k&＃61;segt[1].len;
117 l&＃61;lower_bound(vec&＃43;1,vec&＃43;m&＃43;1,edgey[i].l)-vec;
118 r&＃61;lower_bound(vec&＃43;1,vec&＃43;m&＃43;1,edgey[i].r)-vec;
119 update(1,l,r-1,edgey[i].d);
120 ans&＃43;&＃61;abs(segt[1].len-k);
121 }
122 memcpy(vec,y,sizeof(y));
123 sort(vec&＃43;1,vec&＃43;n&＃43;1);
124 m&＃61;unique(vec&＃43;1,vec&＃43;n&＃43;1)-vec-1;
125 sort(edgex&＃43;1,edgex&＃43;n&＃43;1,cmpx);
126 init(1,1,m);
127 for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
128 if(edgex[i].l<edgex[i].u)
129 {
130 k&＃61;segt[1].len;
131 l&＃61;lower_bound(vec&＃43;1,vec&＃43;m&＃43;1,edgex[i].l)-vec;
132 r&＃61;lower_bound(vec&＃43;1,vec&＃43;m&＃43;1,edgex[i].u)-vec;
133 update(1,l,r-1,edgex[i].d);
134 ans&＃43;&＃61;abs(segt[1].len-k);
135 }
136 printf("%d\n",ans);
137 }
138 return 0;
139 }