Advertisement
Um_nik

Untitled

Jul 18th, 2014
317
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <cstring>
  5. #include <vector>
  6. #include <map>
  7. using namespace std;
  8.  
  9.  
  10. map <vector <int>, int> v2n;
  11.  
  12. const int maxn = 405;
  13. int diff[maxn][maxn];
  14.  
  15.  
  16. int getN(vector <int> v)
  17. {
  18. if (v2n.count(v) == 0)
  19. {
  20. int sz = v2n.size();
  21. v2n[v] = sz;
  22. return sz;
  23. }
  24. return v2n[v];
  25. }
  26.  
  27. int inB(int x, int l, int r)
  28. {
  29. return max(l, min(x, r) );
  30. }
  31.  
  32.  
  33. struct Square
  34. {
  35. int x1, x2, y1, y2;
  36. Square() : x1(), x2(), y1(), y2() {}
  37. Square(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
  38. Square(int x, int y, int l) : x1(x), y1(y), x2(x + l), y2(y + l) {}
  39.  
  40. bool operator == (Square A)
  41. {
  42. return x1 == A.x1 && x2 == A.x2 && y1 == A.y1 && y2 == A.y2;
  43. }
  44.  
  45. int operator - (Square A)
  46. {
  47. A.x1 -= x1;
  48. A.x2 -= x1;
  49. A.y1 -= y1;
  50. A.y2 -= y1;
  51.  
  52. int n = x2 - x1;
  53.  
  54. A.x1 = inB(A.x1, 0, n);
  55. A.x2 = inB(A.x2, 0, n);
  56. A.y1 = inB(A.y1, 0, n);
  57. A.y2 = inB(A.y2, 0, n);
  58.  
  59. vector <int> v;
  60. if (A == Square(0, 0, n) )
  61. {
  62. printf("Empty\n");
  63. return getN(v);
  64. }
  65.  
  66. v.push_back(n);
  67.  
  68. if (A.x1 == A.x2 || A.y1 == A.y2)
  69. {
  70. printf("Square %d\n", n);
  71. return getN(v);
  72. }
  73.  
  74. if (A.x1 == 0 && A.y1 == 0 && A.y2 == n)
  75. {
  76. A.x1 = n - A.x2;
  77. A.x2 = n;
  78. }
  79. if (A.y1 == 0 && A.x1 == 0 && A.x2 == n)
  80. {
  81. A.y1 = n - A.y2;
  82. A.y2 = n;
  83. }
  84.  
  85. v.push_back(A.x1);
  86. v.push_back(A.x2);
  87. v.push_back(A.y1);
  88. v.push_back(A.y2);
  89.  
  90. printf("n = %d, [%d .. %d] x [%d .. %d]\n", n, A.x1, A.x2, A.y1, A.y2);
  91.  
  92. return getN(v);
  93. }
  94.  
  95. void read()
  96. {
  97. int l;
  98. scanf("%d %d %d", &x1, &y1, &l);
  99. x2 = x1 + l;
  100. y2 = y1 + l;
  101. }
  102. };
  103.  
  104.  
  105.  
  106. Square sq[maxn];
  107. int cnt[maxn * maxn];
  108. long long ans = 0;
  109.  
  110. int main()
  111. {
  112. freopen("squares.in", "r", stdin);
  113. freopen("squares.out", "w", stdout);
  114.  
  115. int n;
  116. scanf("%d", &n);
  117. for (int i = 0; i < n; i++)
  118. {
  119. sq[i].read();
  120. }
  121. for (int i = 0; i < n; i++)
  122. for (int j = 0; j < n; j++)
  123. {
  124. if (i == j)
  125. continue;
  126. printf("i = %d, j = %d\n", i, j);
  127. diff[i][j] = sq[i] - sq[j];
  128. ans += cnt[diff[i][j] ];
  129. cnt[diff[i][j] ]++;
  130. }
  131.  
  132. for (int i = 0; i < n; i++)
  133. for (int j = 0; j < n; j++)
  134. {
  135. if (i == j)
  136. continue;
  137. int c = i;
  138. int d = j;
  139. for (int it = 0; it < 2; it++)
  140. {
  141. if (diff[i][j] == diff[c][d] )
  142. ans --;
  143. swap(c, d);
  144. }
  145. }
  146. for (int i = 0; i < n; i++)
  147. for (int j = 0; j < n; j++)
  148. for (int h = 0; h < n; h++)
  149. {
  150. if (i == j || i == h || j == h)
  151. continue;
  152. int a = i;
  153. int b = j;
  154. for (int it1 = 0; it1 < 2; it1++)
  155. {
  156. int c = i;
  157. int d = h;
  158. for (int it2 = 0; it2 < 2; it2++)
  159. {
  160. if (diff[a][b] == diff[c][d] )
  161. ans--;
  162. swap(c, d);
  163. }
  164. swap(a, b);
  165. }
  166. }
  167. printf("%I64d\n", ans);
  168.  
  169. return 0;
  170. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement