HDU_1225

??? 拓展一下求K次覆蓋的矩形的并的話就是UVA_11983那個題了。感覺上用線段樹處理矩形的并，首先就是要標記出哪些區間被覆蓋了，其次就是要用類似dp的思想，用cover[i][j]表示在線段樹上的節點i表示的范圍內，覆蓋了j次的線段總長度，同時cover[i][K]表示的是覆蓋了K次及大于K次的線段的總長度，然后依據左右兒子的狀態來更新cover[i][j]的狀態。

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> #define MAXD 2010 #define zero 1e-8 int N, M, cnt[4 * MAXD], K = 2; double ty[MAXD], cover[4 * MAXD][3]; struct Seg {double x, y1, y2;int col; }seg[MAXD]; int cmpy(const void *_p, const void *_q) {double *p = (double *)_p, *q = (double *)_q;return *p < *q ? -1 : 1; } int cmps(const void *_p, const void *_q) {Seg *p = (Seg *)_p, *q = (Seg *)_q;return p->x < q->x ? -1 : 1; } int dcmp(double x) {return fabs(x) < zero ? 0 : (x < 0 ? -1 : 1); } void build(int cur, int x, int y) {int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;memset(cover[cur], 0, sizeof(cover[cur]));cover[cur][0] = ty[y + 1] - ty[x];cnt[cur] = 0;if(x == y)return ;build(ls, x, mid);build(rs, mid + 1, y); } void init() {int i, j, k;double x1, x2, y1, y2;scanf("%d", &N);for(i = 0; i < N; i ++){j = i << 1, k = (i << 1) | 1;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);seg[j].x = x1, seg[k].x = x2;seg[j].y1 = seg[k].y1 = y1, seg[j].y2 = seg[k].y2 = y2;seg[j].col = 1, seg[k].col = -1;ty[j] = y1, ty[k] = y2;}qsort(ty, N << 1, sizeof(ty[0]), cmpy);M = (N << 1) - 1;build(1, 0, M - 1); } void update(int cur, int x, int y) {int ls = cur << 1, rs = (cur << 1) | 1;memset(cover[cur], 0, sizeof(cover[cur]));if(cnt[cur] >= K)cover[cur][K] = ty[y + 1] - ty[x];else if(x == y)cover[cur][cnt[cur]] = ty[y + 1] - ty[x];else{int i;for(i = cnt[cur]; i <= K; i ++)cover[cur][i] += cover[ls][i - cnt[cur]] + cover[rs][i - cnt[cur]];for(i = K - cnt[cur] + 1; i <= K; i ++)cover[cur][K] += cover[ls][i] + cover[rs][i];} } void refresh(int cur, int x, int y, int s, int t, int c) {int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;if(x >= s && y <= t){cnt[cur] += c;update(cur, x, y);return ;}if(mid >= s)refresh(ls, x, mid, s, t, c);if(mid + 1 <= t)refresh(rs, mid + 1, y, s, t, c);update(cur, x, y); } int BS(double x) {int min = 0, max = M + 1, mid;for(;;){mid = (min + max) >> 1;if(mid == min)break;if(dcmp(ty[mid] - x) <= 0)min = mid;elsemax = mid;}return mid; } void solve() {int i, j, k;double ans = 0;qsort(seg, N << 1, sizeof(seg[0]), cmps);seg[N << 1].x = seg[(N << 1) - 1].x;for(i = 0; i < (N << 1); i ++){j = BS(seg[i].y1), k = BS(seg[i].y2);if(j < k)refresh(1, 0, M - 1, j, k - 1, seg[i].col);ans += cover[1][K] * (seg[i + 1].x - seg[i].x);}printf("%.2f\n", ans); } int main() {int t;scanf("%d", &t);while(t --){init();solve();}return 0; }

總結

以上是生活随笔為你收集整理的HDU 1225 覆盖的面积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。