fork download 
  1. #include<stdio.h>
  2. #include<map>
  3. using namespace std;
  4. map<pair<int, int>, int>M;
  5. int dx[4] = { 1,-1,0,0 };
  6. int dy[4] = { 0,0,1,-1 };
  7. int E[121][121][4];
  8. int name[121][121], par[121212], C[121212];
  9. bool is_gone[121212];
  10. int find(int x) {
  11. 	if (x == par[x])return x;
  12. 	return par[x] = find(par[x]);
  13. }
  14. void union_(int a, int b) {
  15. 	int pa = find(a);
  16. 	int pb = find(b);
  17. 	if (pa == pb)return;
  18. 	par[pa] = pb;
  19. 	C[pb] += C[pa];
  20. }
  21. int main() {
  22. 	int n, k, r, i, j;
  23. 	for (i = 0; i < 4; i++) M[{dx[i], dy[i]}] = i;
  24. 	scanf("%d%d%d", &n, &k, &r);
  25. 	for (i = 0; i < r; i++) {
  26. 		int x1, y1, x2, y2;
  27. 		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  28. 		int dx = x1 - x2;
  29. 		int dy = y1 - y2;
  30. 		E[x1][y1][M[{-dx, -dy}]] = 1;
  31. 		E[x2][y2][M[{dx, dy}]] = 1;
  32. 	}
  33. 	int cnt = 0;
  34. 	for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)name[i][j] = ++cnt, par[cnt] = cnt;
  35. 	for (i = 0; i < k; i++) {
  36. 		int x, y;
  37. 		scanf("%d%d", &x, &y);
  38. 		C[name[x][y]]++;
  39. 	}
  40. 	int ans = k*(k - 1) / 2;
  41. 	for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)for (k = 0; k < 4; k++) {
  42. 		if (E[i][j][k])continue;
  43. 		int nextx = i + dx[k];
  44. 		int nexty = j + dy[k];
  45. 		if (nextx <= 0 || nextx > n || nexty <= 0 || nexty>n)continue;
  46. 		union_(name[i][j], name[nextx][nexty]);
  47. 	}
  48. 	for (i = 1; i <= n*n; i++) {
  49. 		int pa = find(i);
  50. 		if (is_gone[pa])continue;
  51. 		is_gone[pa] = 1;
  52. 		ans -= C[pa] * (C[pa] - 1) / 2;
  53. 	}
  54. 	printf("%d", ans);
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 4464KB
comments (?)
stdin 
3 3 3
2 2 2 3
3 3 3 2
3 3 2 3
3 3
2 2
2 3
stdout 
2
https://ideone.com/dcAB2H
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!