題意：給出每個矩形的左下角，右上角，求所有矩形的並面積，就是不重復計算重復的部分
思路：線段樹的一個應用，還是太年輕，看了別人的方法點擊打開鏈接
#include#include #include #include using namespace std; const int MAXN = 110; struct Line{ double x,y_down,y_up; int flag; bool operator<(const Line &a)const{ return x < a.x; } }line[2*MAXN]; struct Tree{ double y_down,y_up; double x; int cover; bool flag; }tree[1000*MAXN]; int n; double x1,y1,x2,y2; double y[MAXN*2]; void build(int i, int l, int r){ tree[i].x = -1; tree[i].cover = 0; tree[i].y_down = y[l]; tree[i].y_up = y[r]; tree[i].flag = 0; if (l + 1 == r){ tree[i].flag = 1; return; } int mid = (l+r)>>1; build(2*i,l,mid); build(2*i+1,mid,r); } double insert(int i, double x, double l, double r, int flag){ if (r <= tree[i].y_down || l >= tree[i].y_up) return 0; if (tree[i].flag){ if (tree[i].cover > 0){ double temp_x = tree[i].x; double ans = (x-temp_x)*(tree[i].y_up-tree[i].y_down); tree[i].x = x; tree[i].cover += flag; return ans; } else { tree[i].cover += flag; tree[i].x = x; return 0; } } double ans1,ans2; ans1 = insert(2*i, x, l, r, flag); ans2 = insert(2*i+1, x, l, r, flag); return ans1+ans2; } int main(){ int cas = 0; while (scanf("%d",&n) != EOF && n){ int index = 1; for (int i = 1; i <= n; i++){ scanf("%lf%lf%lf%lf",&x1, &y1, &x2, &y2); y[index] = y1; line[index].x = x1; line[index].y_down = y1; line[index].y_up = y2; line[index].flag = 1; index++; y[index] = y2; line[index].x = x2; line[index].y_down = y1; line[index].y_up = y2; line[index].flag = -1; index++; } sort(y+1, y+index); sort(line+1, line+index); build(1,1,index-1); double ans = 0; for (int i = 1; i < index; i++){ ans += insert(1, line[i].x, line[i].y_down, line[i].y_up, line[i].flag); } printf("Test case #%d\nTotal explored area: %.2f\n\n",++cas,ans); } return 0; }
