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