#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define mt make_tuple
int xe, ye, xh, yh, c, d, dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0};
vector<pair<int, int> > hor, ver, mv;
set<pair<int, int> > s;
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> xe >> ye >> xh >> yh >> d;
assert(llabs(xe - xh) != 1 || llabs(ye - yh) != 1);
c = llabs(xe - xh) + llabs(ye - yh);
if ((c > d || (c & 1) ^ (d & 1)) || (c == 1 && c ^ d)) return cout << "impossible\n", 0;
if (yh > ye) {
swap(xe, xh);
swap(ye, yh);
}
if (llabs(xe - xh) == 1 && llabs(ye - yh) == 1) {
if (d == 4) return cout << "impossible\n", 0;
if (d == 2) mv.emplace_back(min(xe, xh), ye);
else {
d -= 6;
int up = d >> 1, down = 2 + (d >> 1);
for (int i = 0; i <= up; i++) mv.emplace_back(xe, ye + i);
if (xe >= xh) {
mv.emplace_back(xe, ye + up + 1);
mv.emplace_back(xe - 1, ye + up + 1);
mv.emplace_back(xe - 2, ye + up + 1);
for (int i = 0; i <= down; i++) mv.emplace_back(xh - 1, yh + i);
} else {
mv.emplace_back(xe, ye + up + 1);
mv.emplace_back(xe + 1, ye + up + 1);
mv.emplace_back(xe + 2, ye + up + 1);
for (int i = 0; i <= down; i++) mv.emplace_back(xh + 1, yh + i);
}
}
} else if (xe == xh) {
for (int i = xe; i < xe + (d - c >> 1); i++) mv.emplace_back(i, ye);
for (int i = ye; i >= yh; i--) mv.emplace_back(xe + (d - c >> 1), i);
for (int i = xe; i < xe + (d - c >> 1); i++) mv.emplace_back(i, yh);
} else if (ye == yh) {
if (xh > xe) swap(xe, xh);
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xe, i);
for (int i = xe; i >= xh; i--) mv.emplace_back(i, ye + (d - c >> 1));
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xh, i);
} else if (xe >= xh) {
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xe, i);
for (int i = xe; i >= xh; i--) mv.emplace_back(i, ye + (d - c >> 1));
for (int i = ye + (d - c >> 1) - 1; i >= yh; i--) mv.emplace_back(xh, i);
} else {
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xe, i);
for (int i = xe; i <= xh; i++) mv.emplace_back(i, ye + (d - c >> 1));
for (int i = ye + (d - c >> 1) - 1; i >= yh; i--) mv.emplace_back(xh, i);
}
sort(mv.begin(), mv.end());
for (auto i : mv)
for (int k = 0; k < 4; k++)
if (!binary_search(mv.begin(), mv.end(), mp(i.first + dr[k], i.second + dc[k]))) s.emplace(i.first + dr[k], i.second + dc[k]);
cout << s.size() << '\n';
for (auto i : s) cout << i.first << ' ' << i.second << '\n';
}
Compilation message
towerdefense.cpp:11:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
towerdefense.cpp: In function 'int main()':
towerdefense.cpp:42:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = xe; i < xe + (d - c >> 1); i++) mv.emplace_back(i, ye);
~~^~~
towerdefense.cpp:43:58: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye; i >= yh; i--) mv.emplace_back(xe + (d - c >> 1), i);
~~^~~
towerdefense.cpp:44:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = xe; i < xe + (d - c >> 1); i++) mv.emplace_back(i, yh);
~~^~~
towerdefense.cpp:47:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xe, i);
~~^~~
towerdefense.cpp:48:61: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = xe; i >= xh; i--) mv.emplace_back(i, ye + (d - c >> 1));
~~^~~
towerdefense.cpp:49:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xh, i);
~~^~~
towerdefense.cpp:51:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xe, i);
~~^~~
towerdefense.cpp:52:61: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = xe; i >= xh; i--) mv.emplace_back(i, ye + (d - c >> 1));
~~^~~
towerdefense.cpp:53:24: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye + (d - c >> 1) - 1; i >= yh; i--) mv.emplace_back(xh, i);
~~^~~
towerdefense.cpp:55:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye; i < ye + (d - c >> 1); i++) mv.emplace_back(xe, i);
~~^~~
towerdefense.cpp:56:61: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = xe; i <= xh; i++) mv.emplace_back(i, ye + (d - c >> 1));
~~^~~
towerdefense.cpp:57:24: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
for (int i = ye + (d - c >> 1) - 1; i >= yh; i--) mv.emplace_back(xh, i);
~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
7 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
4 ms |
384 KB |
Output is correct |
| 14 |
Correct |
4 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
4 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
5 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
5 ms |
384 KB |
Output is correct |
| 24 |
Correct |
5 ms |
384 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
5 ms |
384 KB |
Output is correct |
| 27 |
Incorrect |
5 ms |
384 KB |
Distance from entrance to home is not d. |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
7 ms |
640 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
5 ms |
384 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
5 ms |
384 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
5 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
4 ms |
384 KB |
Output is correct |
| 21 |
Correct |
4 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
5 ms |
384 KB |
Output is correct |
| 24 |
Correct |
5 ms |
384 KB |
Output is correct |
| 25 |
Correct |
5 ms |
384 KB |
Output is correct |
| 26 |
Correct |
4 ms |
384 KB |
Output is correct |
| 27 |
Correct |
5 ms |
384 KB |
Output is correct |
| 28 |
Correct |
5 ms |
384 KB |
Output is correct |
| 29 |
Correct |
5 ms |
384 KB |
Output is correct |
| 30 |
Correct |
5 ms |
384 KB |
Output is correct |
| 31 |
Correct |
5 ms |
384 KB |
Output is correct |
| 32 |
Correct |
5 ms |
384 KB |
Output is correct |
| 33 |
Correct |
5 ms |
384 KB |
Output is correct |
| 34 |
Incorrect |
5 ms |
384 KB |
Distance from entrance to home is not d. |
| 35 |
Halted |
0 ms |
0 KB |
- |
