Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin("date.in");
- ofstream fout("date.out");
- int n, m, i, j, k;
- bool ok = 0;
- struct cladire
- {
- int x, y;
- int arie;
- };
- bool cmp(cladire a, cladire b);
- void initializare(int mat[1001][1001]);
- int dfs1(int x, int y, int height);
- void dfs2(int x, int y, int height);
- long double xsum = 0, ysum = 0, points = 0;
- void afisare(int mat[1001][1001]);
- int a[1001][1001];
- int verif[1001][1001];
- vector<cladire> v;
- int main()
- {
- fin>>n>>m;
- for(i=1; i<=n; i++)
- for(j=1; j<=m; j++)
- fin >> a[i][j];
- for(i=1; i<=n; i++)
- for(j=1; j<=m; j++)
- if(a[i][j] && !verif[i][j])
- v.push_back({i, j, dfs1(i, j, a[i][j])});
- sort(v.begin(), v.end(), cmp);
- fin >> k;
- for(int l=1; l<=k; l++)
- {
- int id1, id2;
- long double xcentre1, ycentre1, xcentre2, ycentre2;
- fin >> id1 >> id2;
- initializare(verif);
- //centre1
- xsum = 0, ysum = 0, points = 0;
- dfs2(v[id1].x, v[id1].y, a[v[id1].x][v[id1].y]);
- xcentre1 = (long double)(xsum/points);
- ycentre1 = (long double)(ysum/points);
- //centre2
- xsum = 0, ysum = 0, points = 0;
- dfs2(v[id2].x, v[id2].y, a[v[id2].x][v[id2].y]);
- xcentre2 = (long double)(xsum/points);
- ycentre2 = (long double)(ysum/points);
- cout << xcentre1 << ' ' << ycentre1 << '\n';
- cout << xcentre2 << ' ' << ycentre2 << '\n';
- cout << '\n';
- }
- return 0;
- }
- void dfs2(int x, int y, int height)
- {
- if(a[x][y] == 0 or a[x][y]!=height or verif[x][y])
- return ;
- else
- {
- verif[x][y] = 1;
- xsum+=x;
- ysum+=y;
- points++;
- dfs2(x+1, y, height);
- dfs2(x, y+1, height);
- dfs2(x, y-1, height);
- dfs2(x-1, y, height);
- }
- }
- bool cmp(cladire a, cladire b)
- {
- return (a.arie < b.arie);
- }
- void afisare(int mat[1001][1001])
- {
- for(int i=1; i<=n; i++)
- {
- for(j=1; j<=m; j++)
- cout << mat[i][j] << ' ';
- cout << '\n';
- }
- }
- void initializare(int mat[1001][1001])
- {
- for(int i=1; i<=n; i++)
- for(int j=1; j<=m; j++)
- mat[i][j] = 0;
- }
- int dfs1(int x, int y, int height)
- {
- if(a[x][y] == 0 or a[x][y] != height or verif[x][y])
- return 0;
- else
- {
- verif[x][y] = 1;
- int sol=1+dfs1(x+1, y, height)+ dfs1(x, y+1, height)+ dfs1(x-1, y, height)+ dfs1(x, y-1, height);
- return sol;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement