鏈接：https://www.nowcoder.com/acm/contest/163/F

來源：牛客網

2018 ACM 國際大學生程序設計競賽上海大都會賽重現賽 F Color it

時間限制：C/C++ 3秒，其他語言6秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld

題目描述

There is a matrix A that has N rows and M columns. Each grid (i,j)(0 ≤ i < N, 0 ≤ j < M)?is painted in white at first.
Then we perform q operations:
For each operation, we are given (x_c, y_c) and r. We will paint all grids (i, j) that meets to black.
You need to calculate the number of white grids left in matrix A.

輸入描述:

The first line of the input is T(1≤ T ≤ 40), which stands for the number of test cases you need to solve. The first line of each case contains three integers N, M and q (1 ≤ N, M ≤ 2 x 10⁴; 1 ≤ q ≤ 200), as mentioned above. The next q lines, each lines contains three integers?x _c, y _c and r (0 ≤ x _c < N; 0 ≤ y _c < M; 0 ≤ r ≤ 10 ⁵), as mentioned above.

輸出描述:

For each test case, output one number. 示例1

輸入

復制 2 39 49 2 12 31 6 15 41 26 1 1 1 0 0 1

輸出

復制 729 0

---

題意還是比較簡單的，給你n和m的格子讓你去畫圓，如果這個點在圓內，就要被染色，問你還剩多少點沒有被染色

這個題目可以直接暴力掃描線，也就成了維護線段的并

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; vector<pair<int,int> >V[N]; int main() {int T;scanf("%d",&T);while(T--){for(int i=0; i<N; i++)V[i].clear();int n,m,q;scanf("%d%d%d",&n,&m,&q);for(int j=0,x,y,r; j<q; j++){scanf("%d%d%d",&x,&y,&r);for(int i=max(0,y-r),d; i<=min(m-1,y+r); i++)d=(sqrt(r*r-(y-i)*(y-i)+1e-6)),V[i].push_back(make_pair(max(0,x-d),min(x+d,n-1)));}int s=n*m;for(int i=0; i<m; i++){int l=V[i].size();if(l>0){sort(V[i].begin(),V[i].end());int r=-1;for(auto X:V[i]){if(X.second<=r)continue;if(X.first>r) s-=X.second-X.first+1;else s-=X.second-r;r=X.second;}}}cout<<s<<"\n";}return 0; }

?

轉載于:https://www.cnblogs.com/BobHuang/p/9493577.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛 F Color it的全部內容，希望文章能夠幫你解決所遇到的問題。

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