// Author: Piotr Grzegorczyk (ud2@interia.eu) // Task: PA2018/RYK // NOTE: od tak rzutem na tasme O(n^3) #include <bits/stdc++.h> using namespace std; int vdr[8] = {1, 1, 0, -1, -1, -1, 0, 1}; int vdc[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int main() { // freopen("ryk.in", "rb", stdin); vector<int> vr, vc; int n; scanf("%d", &n); for (int i=0; i<n; i++) { int r, c; scanf("%d%d", &r, &c); vr.push_back(r); vc.push_back(c); } for (int k=0; k<n; k++) { vector<int> vr2(vr), vc2(vc); for (int i=0; i<n; i++) { // ryczacy if (i==k) continue; for (int j=0; j<n; j++) { // biezacy if (j==k) continue; int r = vr2[j]; int c = vc2[j]; int d2 = 1ll*(r - vr2[i])*(r - vr2[i]) + 1ll*(c - vc2[i])*(c - vc2[i]); for (int d=0; d<8; d++) { int rd = vr2[j] + vdr[d]; int cd = vc2[j] + vdc[d]; int dd = 1ll*(rd - vr2[i])*(rd - vr2[i]) + 1ll*(cd - vc2[i])*(cd - vc2[i]); if (dd < d2) { r = rd; c = cd; d2 = dd; } } vr2[j] = r; vc2[j] = c; } } long long R = 0; for (int i=0; i<n; i++) R += 1ll*vr2[i]*vc2[i]; printf("%lld\n", R); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | // Author: Piotr Grzegorczyk (ud2@interia.eu) // Task: PA2018/RYK // NOTE: od tak rzutem na tasme O(n^3) #include <bits/stdc++.h> using namespace std; int vdr[8] = {1, 1, 0, -1, -1, -1, 0, 1}; int vdc[8] = {0, 1, 1, 1, 0, -1, -1, -1}; int main() { // freopen("ryk.in", "rb", stdin); vector<int> vr, vc; int n; scanf("%d", &n); for (int i=0; i<n; i++) { int r, c; scanf("%d%d", &r, &c); vr.push_back(r); vc.push_back(c); } for (int k=0; k<n; k++) { vector<int> vr2(vr), vc2(vc); for (int i=0; i<n; i++) { // ryczacy if (i==k) continue; for (int j=0; j<n; j++) { // biezacy if (j==k) continue; int r = vr2[j]; int c = vc2[j]; int d2 = 1ll*(r - vr2[i])*(r - vr2[i]) + 1ll*(c - vc2[i])*(c - vc2[i]); for (int d=0; d<8; d++) { int rd = vr2[j] + vdr[d]; int cd = vc2[j] + vdc[d]; int dd = 1ll*(rd - vr2[i])*(rd - vr2[i]) + 1ll*(cd - vc2[i])*(cd - vc2[i]); if (dd < d2) { r = rd; c = cd; d2 = dd; } } vr2[j] = r; vc2[j] = c; } } long long R = 0; for (int i=0; i<n; i++) R += 1ll*vr2[i]*vc2[i]; printf("%lld\n", R); } return 0; } |