Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define MAX 1005
- int n, m, k;
- vector<pair<int, int> > V;
- vector<int> X;
- vector<int> Y;
- map<int, int> mpX, mpY;
- map<int, int> revX, revY;
- int grid[MAX][MAX];
- bool vis[MAX][MAX];
- int calcVer(int x1, int x2)
- {
- if(x1 == 0 || x2 == 0) return 0;
- int p = revX[x1];
- int q = revX[x2];
- return abs(p-q);
- }
- int calcHor(int y1, int y2)
- {
- if(y1 == 0 || y2 == 0) return 0;
- int p = revY[y1];
- int q = revY[y2];
- return abs(p-q);
- }
- int calcAll(int x1, int y1, int x2, int y2)
- {
- if(x1 == 0 || y1 == 0 || x2 == 0 || y2 == 0) return 0;
- x1 = revX[x1];
- x2 = revX[x2];
- y1 = revY[y1];
- y2 = revY[y2];
- return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
- }
- int main()
- {
- int cases;
- scanf("%d", &cases);
- while(cases--){
- scanf("%d %d %d", &n, &m, &k);
- for(int i=0; i<k; i++){
- int x, y;
- scanf("%d %d", &x, &y);
- V.push_back(make_pair(x, y));
- X.push_back(x);
- Y.push_back(y);
- }
- sort(X.begin(), X.end());
- sort(Y.begin(), Y.end());
- int idx = 0;
- for(int i=0; i<X.size(); i++){
- int v = X[i];
- if(mpX[v] == 0){
- idx++;
- mpX[v] = idx;
- revX[idx] = v;
- }
- }
- int idy = 0;
- for(int i=0; i<Y.size(); i++){
- int v = Y[i];
- if(mpY[v] == 0){
- idy++;
- mpY[v] = idy;
- revY[idy] = v;
- }
- }
- memset(grid, 0, sizeof grid);
- memset(vis, false, sizeof vis);
- for(int i=0; i<k; i++){
- int x = V[i].first;
- int y = V[i].second;
- x = mpX[x];
- y = mpY[y];
- vis[x][y] = true;
- grid[x][y] = 1;
- }
- long long odd = 0, even = 0;
- for(int i=1; i<=idx; i++){
- for(int j=1; j<=idy; j++){
- int cur = i*j;
- cur = cur%2;
- if(cur) odd++;
- else even++;
- if(cur == 1){
- even += calcAll(i, j, i-1, j-1);
- }
- else {
- odd += calcAll(i, j, i-1, j-1);
- }
- cur = (i-1)*j;
- cur = cur%2;
- if(cur == 1){
- odd += calcVer(i, i-1);
- }
- else {
- even += calcVer(i, i-1);
- }
- cur = i*(j-1);
- if(cur == 1){
- odd += calcHor(j, j-1);
- }
- else {
- even += calcHor(j, j-1);
- }
- }
- }
- if(idx == 0) idx = 1;
- if(idy == 0) idy = 1;
- cout << odd << " " << even << endl;
- int tot = idx*idy;
- tot = tot%2;
- int sum = (n-idx+1)*(m-idy+1);
- sum = sum-1;
- if(tot == 0) even += sum;
- else odd += sum;
- cout << odd << " " << even << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement