2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，
后面的每日一題，每題發一個新博文，請大家看博客目錄：https://blog.csdn.net/weixin_43914593
文章目錄
- 1、題目描述
- 2、題解
- 3、暴力
- 3、標準解法
2017省賽A類第10題，最后一題，題目鏈接：
油漆面積 http://oj.ecustacm.cn/problem.php?id=1324
1、題目描述
平面上有n個矩形，給出每個矩形的坐標，這些矩形可能有重疊，
問這些矩形覆寫的總面積是多少，
資料規模：1<=n<10000，坐標0<= x1,y1,x2,y2 <=10000
資源約定：記憶體 < 256M；CPU < 2000ms
2、題解
??本題是一個經典問題：“矩形面積并”，
??首先給出兩種暴力法，
??（1）先單獨求每個矩形的面積，然后把所有矩形的面積加起來，最后減去任意兩個矩形的交集，求矩形的交集很花時間，需要兩兩配對，復雜度
O
(
n
2
)
O(n^2)
O(n2)，
??（2）另一種更簡單的暴力法，是把平面劃成單位邊長為1（面積也是1）的方格，每讀入一個矩形，就把它覆寫的方格標注為已覆寫；對所有矩形都這樣處理，最后統計被覆寫的方格數量即可，編碼極其簡單，但是比上一種方法更慢，且消耗極大的空間，
??本題的資料非常弱：矩形數量少，坐標值也不大，用第（2）種暴力法，也能通過，對，就這么干！
3、暴力
#include<bits/stdc++.h>
using namespace std;
bool vis[10001][10001]; //100M記憶體
int main(){
int n,sum=0; //sum：面積
scanf("%d",&n);
for(int k=0;k<n;k++){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2); //讀一個矩形
if(x1>x2) swap(x1,x2); //坐標排序
if(y1>y2) swap(y1,y2);
for(int i=x1;i<x2;i++) //統計這個矩形覆寫的面積
for(int j=y1;j<y2;j++)
if(!vis[i][j]){ //沒有被覆寫過
sum++; //統計面積
vis[i][j]=1; //標注為已經覆寫
}
}
cout<<sum;
return 0;
}
3、標準解法
??當n很大，n<100000，且坐標值很大時，暴力法顯然會超時，
??“矩形面積并”的標準解法是線段樹的掃描線，建模和編碼可不容易，參考博文“線段樹”：
??https://blog.csdn.net/weixin_43914593/article/details/108221534
??其中的“7.1 矩形面積并”，和本題完全相同，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/248094.html
標籤：其他
上一篇：PS基礎知識大雜燴