Advertisement
GerONSo

Untitled

Dec 23rd, 2018
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.51 KB | None | 0 0
  1. /*
  2. ┓┏┓┏┓┃
  3. ┛┗┛┗┛┃
  4. ┓┏┓┏┓┃
  5. ┛┗┛┗┛┃
  6. ┓┏┓┏┓┃\○/
  7. ┛┗┛┗┛┃ / /
  8. ┓┏┓┏┓┃ノ
  9. ┛┗┛┗┛┃
  10. ┓┏┓┏┓┃
  11. ┛┗┛┗┛┃
  12. ┓┏┓┏┓┃
  13. ┛┗┛┗┛┃
  14. ┓┏┓┏┓┃
  15. ┛┗┛┗┛┃
  16. ┓┏┓┏┓┃┓
  17. ┛┗┛┗┛┃┃
  18. MIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSIC
  19. */
  20.  
  21. // #define pragma
  22.  
  23. #ifdef pragma
  24. #pragma GCC optimize("Ofast")
  25. #pragma GCC optimize("no-stack-protector")
  26. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  27. #pragma GCC optimize("unroll-loops")
  28. #pragma GCC diagnostic ignored "-Wunused-result"
  29. #endif // pragma
  30.  
  31. #include<bits/stdc++.h>
  32. #include <ext/pb_ds/assoc_container.hpp>
  33. #include <ext/pb_ds/tree_policy.hpp>
  34.  
  35. #define ll long long
  36. #define all(x) begin(x), end(x)
  37. #define pb push_back
  38. #define x first
  39. #define y second
  40. #define int long long
  41. #define zero(two) memset(two, 0, sizeof(two))
  42.  
  43. using namespace std;
  44. using namespace __gnu_pbds;
  45.  
  46.  
  47. typedef vector<int> vi;
  48. typedef vector<bool> vb;
  49. typedef pair<int, int> pii;
  50. typedef long double ld;
  51. typedef vector<vi> matrix;
  52. template<typename T>
  53. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  54.  
  55. const ld PI = atan2(0, -1);
  56.  
  57. void seriy() {
  58. ios::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. cout << fixed << setprecision(10);
  62. #if 0
  63. freopen("input", "r", stdin);
  64. freopen("output", "w", stdout);
  65. #endif
  66. }
  67.  
  68. const int MAXN = 1010;
  69. const int INF = 1e9 + 7;
  70.  
  71. bool used[MAXN][MAXN];
  72. pii pr[MAXN][MAXN];
  73. vi dx = {-1, 1, 0, 0};
  74. vi dy = {0, 0, -1, 1};
  75. set<pii> ress;
  76. int mn = INF;
  77. pii a, b, c;
  78.  
  79. void solve() {
  80. queue<pii> q;
  81. q.push(a);
  82. zero(used);
  83. zero(pr);
  84. used[a.x][a.y] = 1;
  85. pr[a.x][a.y] = {-1, -1};
  86. while(!q.empty()) {
  87. pii u = q.front();
  88. q.pop();
  89. if(u == b) {
  90. break;
  91. }
  92. for(int k = 0; k < 4; k++) {
  93. int tx = u.x + dx[k];
  94. int ty = u.y + dy[k];
  95. if(tx > -1 && ty > -1 && tx < MAXN && ty < MAXN && !used[tx][ty]) {
  96. used[tx][ty] = 1;
  97. pr[tx][ty] = u;
  98. q.push({tx, ty});
  99. }
  100. }
  101. }
  102. vector<pii> ans1, ans2, ans3;
  103. pii cur = b;
  104. while(cur != pii{-1, -1}) {
  105. ans1.pb(cur);
  106. cur = pr[cur.x][cur.y];
  107. }
  108. zero(used);
  109. zero(pr);
  110. queue<pii> qq;
  111. swap(q, qq);
  112. q.push(a);
  113. used[a.x][a.y] = 1;
  114. pr[a.x][a.y] = {-1, -1};
  115. while(!q.empty()) {
  116. pii u = q.front();
  117. // cerr << u.x << " " << u.y << '\n';
  118. q.pop();
  119. if(u == c) {
  120. break;
  121. }
  122. for(int k = 0; k < 4; k++) {
  123. int tx = u.x + dx[k];
  124. int ty = u.y + dy[k];
  125. if(tx > -1 && ty > -1 && tx < MAXN && ty < MAXN && !used[tx][ty]) {
  126. used[tx][ty] = 1;
  127. pr[tx][ty] = u;
  128. q.push({tx, ty});
  129. }
  130. }
  131. }
  132. // for(int i = 0; i < 5; i++) {
  133. // for(int j = 0; j < 5; j++) {
  134. // cerr << i << " " << j << " " << pr[i][j].x << " " << pr[i][j].y << '\n';
  135. // }
  136. // }
  137. cur = c;
  138. while(cur != pii{-1, -1}) {
  139. ans2.pb(cur);
  140. cur = pr[cur.x][cur.y];
  141. }
  142.  
  143. zero(used);
  144. zero(pr);
  145. queue<pii> qqq;
  146. swap(q, qqq);
  147. q.push(b);
  148. pr[b.x][b.y] = {-1, -1};
  149. used[b.x][b.y] = 1;
  150. while(!q.empty()) {
  151. pii u = q.front();
  152. q.pop();
  153. if(u == c) {
  154. break;
  155. }
  156. for(int k = 0; k < 4; k++) {
  157. int tx = u.x + dx[k];
  158. int ty = u.y + dy[k];
  159. if(tx > -1 && ty > -1 && tx < MAXN && ty < MAXN && !used[tx][ty]) {
  160. used[tx][ty] = 1;
  161. pr[tx][ty] = u;
  162. q.push({tx, ty});
  163. }
  164. }
  165. }
  166. cur = c;
  167. while(cur != pii{-1, -1}) {
  168. ans3.pb(cur);
  169. cur = pr[cur.x][cur.y];
  170. }
  171. set<pii> res1, res2, res3;
  172. for(auto i : ans1) {
  173. res1.insert(i);
  174. }
  175. for(auto i : ans2) {
  176. res1.insert(i);
  177. }
  178.  
  179. for(auto i : ans1) {
  180. res2.insert(i);
  181. }
  182. for(auto i : ans3) {
  183. res2.insert(i);
  184. }
  185.  
  186. for(auto i : ans2) {
  187. res3.insert(i);
  188. }
  189. for(auto i : ans3) {
  190. res3.insert(i);
  191. }
  192. if((int)res1.size() < mn) {
  193. mn = res1.size();
  194. ress.swap(res1);
  195. }
  196. if((int)res2.size() < mn) {
  197. mn = res2.size();
  198. ress.swap(res2);
  199. }
  200. if((int)res3.size() < mn) {
  201. mn = res3.size();
  202. ress.swap(res3);
  203. }
  204. }
  205.  
  206. signed main() {
  207. seriy();
  208.  
  209. map<int, int> mp;
  210. mp[dx[0]] = dy[0];
  211. mp[dx[1]] = dy[1];
  212. mp[dx[2]] = dy[2];
  213. mp[dx[3]] = dy[3];
  214. cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
  215. do {
  216. bool f = 0;
  217. for(int k = 0; k < 4; k++) {
  218. if(f && dx[k] == 0) {
  219. dy[k] = -1;
  220. }
  221. else if(!f && dx[k] == 0) {
  222. f = 1;
  223. dy[k] = 1;
  224. }
  225. else {
  226. dy[k] = mp[dx[k]];
  227. }
  228. // cerr << dx[k] << " " << dy[k] << '\n';
  229. }
  230. // cerr << '\n';
  231. solve();
  232. } while(next_permutation(all(dx)));
  233. cout << ress.size() << '\n';
  234. for(auto i : ress) {
  235. cout << i.x << " " << i.y << '\n';
  236. }
  237. return 0;
  238. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement