Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃\○/
- ┛┗┛┗┛┃ / /
- ┓┏┓┏┓┃ノ
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃
- ┛┗┛┗┛┃
- ┓┏┓┏┓┃┓
- ┛┗┛┗┛┃┃
- MIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSIC
- */
- // #define pragma
- #ifdef pragma
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("no-stack-protector")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #pragma GCC optimize("unroll-loops")
- #pragma GCC diagnostic ignored "-Wunused-result"
- #endif // pragma
- #include<bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define ll long long
- #define all(x) begin(x), end(x)
- #define pb push_back
- #define x first
- #define y second
- #define int long long
- #define zero(two) memset(two, 0, sizeof(two))
- using namespace std;
- using namespace __gnu_pbds;
- typedef vector<int> vi;
- typedef vector<bool> vb;
- typedef pair<int, int> pii;
- typedef long double ld;
- typedef vector<vi> matrix;
- template<typename T>
- using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- const ld PI = atan2(0, -1);
- void seriy() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cout << fixed << setprecision(10);
- #if 0
- freopen("input", "r", stdin);
- freopen("output", "w", stdout);
- #endif
- }
- const int MAXN = 1010;
- const int INF = 1e9 + 7;
- bool used[MAXN][MAXN];
- pii pr[MAXN][MAXN];
- vi dx = {-1, 1, 0, 0};
- vi dy = {0, 0, -1, 1};
- set<pii> ress;
- int mn = INF;
- pii a, b, c;
- void solve() {
- queue<pii> q;
- q.push(a);
- zero(used);
- zero(pr);
- used[a.x][a.y] = 1;
- pr[a.x][a.y] = {-1, -1};
- while(!q.empty()) {
- pii u = q.front();
- q.pop();
- if(u == b) {
- break;
- }
- for(int k = 0; k < 4; k++) {
- int tx = u.x + dx[k];
- int ty = u.y + dy[k];
- if(tx > -1 && ty > -1 && tx < MAXN && ty < MAXN && !used[tx][ty]) {
- used[tx][ty] = 1;
- pr[tx][ty] = u;
- q.push({tx, ty});
- }
- }
- }
- vector<pii> ans1, ans2, ans3;
- pii cur = b;
- while(cur != pii{-1, -1}) {
- ans1.pb(cur);
- cur = pr[cur.x][cur.y];
- }
- zero(used);
- zero(pr);
- queue<pii> qq;
- swap(q, qq);
- q.push(a);
- used[a.x][a.y] = 1;
- pr[a.x][a.y] = {-1, -1};
- while(!q.empty()) {
- pii u = q.front();
- // cerr << u.x << " " << u.y << '\n';
- q.pop();
- if(u == c) {
- break;
- }
- for(int k = 0; k < 4; k++) {
- int tx = u.x + dx[k];
- int ty = u.y + dy[k];
- if(tx > -1 && ty > -1 && tx < MAXN && ty < MAXN && !used[tx][ty]) {
- used[tx][ty] = 1;
- pr[tx][ty] = u;
- q.push({tx, ty});
- }
- }
- }
- // for(int i = 0; i < 5; i++) {
- // for(int j = 0; j < 5; j++) {
- // cerr << i << " " << j << " " << pr[i][j].x << " " << pr[i][j].y << '\n';
- // }
- // }
- cur = c;
- while(cur != pii{-1, -1}) {
- ans2.pb(cur);
- cur = pr[cur.x][cur.y];
- }
- zero(used);
- zero(pr);
- queue<pii> qqq;
- swap(q, qqq);
- q.push(b);
- pr[b.x][b.y] = {-1, -1};
- used[b.x][b.y] = 1;
- while(!q.empty()) {
- pii u = q.front();
- q.pop();
- if(u == c) {
- break;
- }
- for(int k = 0; k < 4; k++) {
- int tx = u.x + dx[k];
- int ty = u.y + dy[k];
- if(tx > -1 && ty > -1 && tx < MAXN && ty < MAXN && !used[tx][ty]) {
- used[tx][ty] = 1;
- pr[tx][ty] = u;
- q.push({tx, ty});
- }
- }
- }
- cur = c;
- while(cur != pii{-1, -1}) {
- ans3.pb(cur);
- cur = pr[cur.x][cur.y];
- }
- set<pii> res1, res2, res3;
- for(auto i : ans1) {
- res1.insert(i);
- }
- for(auto i : ans2) {
- res1.insert(i);
- }
- for(auto i : ans1) {
- res2.insert(i);
- }
- for(auto i : ans3) {
- res2.insert(i);
- }
- for(auto i : ans2) {
- res3.insert(i);
- }
- for(auto i : ans3) {
- res3.insert(i);
- }
- if((int)res1.size() < mn) {
- mn = res1.size();
- ress.swap(res1);
- }
- if((int)res2.size() < mn) {
- mn = res2.size();
- ress.swap(res2);
- }
- if((int)res3.size() < mn) {
- mn = res3.size();
- ress.swap(res3);
- }
- }
- signed main() {
- seriy();
- map<int, int> mp;
- mp[dx[0]] = dy[0];
- mp[dx[1]] = dy[1];
- mp[dx[2]] = dy[2];
- mp[dx[3]] = dy[3];
- cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
- do {
- bool f = 0;
- for(int k = 0; k < 4; k++) {
- if(f && dx[k] == 0) {
- dy[k] = -1;
- }
- else if(!f && dx[k] == 0) {
- f = 1;
- dy[k] = 1;
- }
- else {
- dy[k] = mp[dx[k]];
- }
- // cerr << dx[k] << " " << dy[k] << '\n';
- }
- // cerr << '\n';
- solve();
- } while(next_permutation(all(dx)));
- cout << ress.size() << '\n';
- for(auto i : ress) {
- cout << i.x << " " << i.y << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement