描述

輸入n個矩形，求他們總共占地面積（也就是求一下面積的并）
http://codevs.cn/problem/3044/

---

分析

先貼個Matrix67的講離散化的博客地址: http://www.matrix67.com/blog/archives/108
其實上面的博客講的講的就很清楚了.

就相當于把矩形用許多小矩形來代替. 這些小矩形都是有一邊或幾條邊延長后過其他矩形的頂點. 這么一說好像更復雜了. 換個說法, 就是把所有矩形的邊都作為可無限延長的分割線, 將所有矩形分割成小矩形. 每個小矩形作為一個新的點, 然后在bool數組里記錄哪個點被覆蓋, 可以通過預處理或者臨時計算出小矩形的面積. 最后掃一遍統計結果.

---

代碼

49ms 256kB

#include <cstdio> #include <cstring> #include <algorithm> using namespace std;const int maxn = 100 + 10; struct Matrix {double x1, y1, x2, y2; } matrixs[maxn];double x[maxn<<1], y[maxn<<1]; bool covered[maxn<<1][maxn<<1];int main() {int n;while(scanf("%d", &n) == 1) {if(n == 0) break;for(int i = 0; i < n; i++) {double x1, y1, x2, y2;scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);matrixs[i] = (Matrix) {x1, y1, x2, y2};x[i<<1] = x1;y[i<<1] = y1;x[(i<<1) ^ 1] = x2;y[(i<<1) ^ 1] = y2;}sort(x, x + 2*n);sort(y, y + 2*n);// 以左下點的坐標作為格子的編號.memset(covered, 0, sizeof(covered));for(int cur = 0; cur < n; cur++) {int s_x, s_y, t_x, t_y;Matrix& M = matrixs[cur];for(s_x = 0; x[s_x] < M.x1; s_x++);for(s_y = 0; y[s_y] < M.y1; s_y++);for(t_x = s_x; x[t_x] < M.x2; t_x++);for(t_y = s_y; y[t_y] < M.y2; t_y++);// coverfor(int i = s_x; i < t_x; i++)for(int j = s_y; j < t_y; j++)covered[i][j] = 1;}double ans = 0.00;for(int i = 0; i < 2*n - 1; i++)for(int j = 0; j < 2*n - 1; j++)if(covered[i][j]) ans += (x[i + 1]-x[i]) * (y[j + 1]-y[j]);printf("%.2lf\n", ans);}return 0; }

主頁

http://blog.csdn.net/qq_21110267

總結

以上是生活随笔為你收集整理的[CODEVS 3044] 矩形面积求并的全部內容，希望文章能夠幫你解決所遇到的問題。

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