| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
线段树+扫描线,代码如下#include <iostream>
#include <cstdio>
#include <algorithm>
#define M 1000
using namespace std;
struct node
{
int l,r;
int cov;
double len;
};
struct line
{
double x;
double y1;
double y2;
char f;
};
struct line_cmp
{
bool operator()(const line& a, const line& b)
{
return a.x < b.x;
}
};
class seg_tree
{
private:
node tree[M];
double number[M]; //the true value of the index l, r and mid
size_t ncount; //the number of nodes in the tree
public:
seg_tree(const double * a, int len);
void build(int l, int r, int root);
void del(int l, int r, int p);
void insert(int l, int r, int p);
double get_len() { return tree[1].len; }
};
seg_tree::seg_tree(const double * a, int len)
{
for(size_t i=0; i<len; i++)
number[i] = a[i];
ncount = len;
build(0, len-1, 1); //build the seg tree
}
void seg_tree::build(int l, int r, int root)
{
tree[root].l = l;
tree[root].r = r;
tree[root].cov = 0;
tree[root].len = 0;
if(l + 1 == r)
return;
int mid = (l + r) >> 1;
build(l, mid, 2*root);
build(mid, r, 2*root+1);
}
void seg_tree::del(int l, int r, int p)
{
if(tree[p].l == l && tree[p].r == r)
{
tree[p].cov --;
if(tree[p].cov <= 0)
{
if(tree[p].l + 1 < tree[p].r)
tree[p].len = tree[2*p].len + tree[2*p+1].len;
else
tree[p].len = 0;
}
return;
}
else
{
int mid = (tree[p].l + tree[p].r) >> 1;
if( r <= mid)
del(l, r, 2*p);
else if(l >= mid)
del(l, r, 2*p+1);
else
{
del(l, mid, 2*p);
del(mid, r, 2*p+1);
}
if(tree[p].cov == 0)
tree[p].len = tree[2*p].len + tree[2*p+1].len;
}
}
void seg_tree::insert(int l, int r, int p)
{
if(tree[p].l == l && tree[p].r == r)
{
tree[p].cov ++;
tree[p].len = number[r] - number[l];
return;
}
else
{
int mid = (tree[p].l + tree[p].r) >> 1;
if(r <= mid)
insert(l, r, 2*p);
else if(l >= mid)
insert(l, r, 2*p+1);
else
{
insert(l, mid, 2*p);
insert(mid, r, 2*p+1);
}
if(tree[p].cov==0)
tree[p].len = tree[2*p].len + tree[2*p+1].len;
}
}
int main()
{
int n;
size_t test_count = 0;
double x1, y1, x2, y2;
double yval[M];
line data[M];
while(cin >> n && n != 0)
{
test_count ++;
int l1 = 0;
int l2 = 0;
for(int i=0; i<n; i++)
{
cin >> x1 >> y1 >> x2 >> y2;
yval[l1++] = y1;
yval[l1++] = y2;
data[l2].x = x1;
data[l2].y1 = y1;
data[l2].y2 = y2;
data[l2].f = -1;
l2 ++;
data[l2].x = x2;
data[l2].y1 = y1;
data[l2].y2 = y2;
data[l2].f = 1;
l2 ++;
}
sort(yval, yval+l1);
sort(data, data+l2, line_cmp());
l1 = unique(yval, yval+l1) - yval;
double sum = 0;
seg_tree stree(yval, l1);
for(int i=0; i<l2-1; i++)
{
int l, r;
l = lower_bound(yval, yval + l1, data[i].y1) - yval;
r = lower_bound(yval, yval + l1, data[i].y2) - yval;
if(data[i].f == -1)
stree.insert(l, r, 1);
else
stree.del(l, r, 1);
sum += stree.get_len() * (data[i+1].x - data[i].x);
}
printf("Test case #%d\n", test_count);
printf("Total explored area: ");
printf("%.2f", sum);
printf("\n\n");
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator