CodeForces 610D Vika and Segments

模板题,矩形面积并

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 220000
#define lson l,m,rt << 1
#define rson m + 1,r,rt << 1 | 1
#define eps 1e-15
using namespace std;
struct seg
{
double l,r,y;
int sign;
seg() {}
seg(double a, double b, double h, int s): l(a), r(b),y(h),sign(s) {}
bool operator < (const seg &cmp) const
{
if(cmp.y == y) return sign > cmp.sign;
return y < cmp.y;
}
} p[ (maxn << )+ ]; double sum[ (maxn << )+ ];
int cnt[ (maxn << ) + ]; double X[ (maxn << ) + ]; void push_up(int rt,int l, int r)
{
if(cnt[rt]) sum[rt] = X[r + ] - X[l]; else if(l == r) sum[rt] = 0.0; else sum[rt] = sum[rt << ] + sum[rt << | ];
}
void update(int L, int R, int cc, int l , int r, int rt)
{
if(L <= l && r <= R)
{
cnt[rt] += cc;
push_up(rt,l,r);
return ;
}
int m = (l + r) >> ;
if(L <= m) update(L,R,cc,lson);
if(R > m) update(L,R,cc,rson);
push_up(rt,l,r);
}
int bin(int low, int high, double key)
{
int mid ;
while(low < high)
{
mid = (low + high) >> ;
if(X[mid] < key ) low = mid + ;
else high = mid;
}
return low;
}
int main()
{
int n,m,k,pp,ca = ;
double a,b,c,d,ret;
while(scanf("%d",&n) != EOF && n)
{
memset(sum,,sizeof(sum));
memset(cnt,,sizeof(cnt));
m = k = ;
ret = 0.0;
pp = ; for(int i = ; i < n; i ++)
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
if(b==d)
{
if(a>c) swap(a,c);
}
else if(a==c)
{
if(b>d) swap(b,d);
}
c++;
d++;
X[m ++] = a;
X[m ++] = c; p[k ++] = seg(a,c,b,); p[k ++] = seg(a,c,d,-);
}
sort(X,X + m);
sort(p,p + k); for(int i = ; i < m; i ++)
if(X[i - ] != X[i])
{
X[pp ++] = X[i];
} pp --;
for(int i = ; i < k - ; i ++)
{
int l = bin(, pp , p[i].l);
int r = bin(, pp , p[i].r) - ;
if(l <= r) update(l,r,p[i].sign,,pp,);
ret += (p[i + ].y - p[i].y) * sum[];
}
printf("%.0f\n",ret);
}
return ;
}
上一篇:听说同学你搞不懂Java的LinkedHashMap,可笑


下一篇:Jquery实现的几款漂亮的时间轴