day08b.cpp (1529B)
1 #include <algorithm> 2 #include <iostream> 3 #include <map> 4 #include <set> 5 #include <sstream> 6 #include <string> 7 #include <string_view> 8 #include <vector> 9 using namespace std; 10 11 #define N 50 12 #define M 50 13 14 bool in_range(int x, int y) { 15 return x >= 0 && x < N && y >= 0 && y < M; 16 } 17 18 vector<pair<int, int>> antinode_all(pair<int, int> p, pair<int, int> q) { 19 auto [xp, yp] = p; 20 auto [xq, yq] = q; 21 /* In theory these two coefficients must be divided by the gcd of 22 * of the coordinates, which leads to possibly more points, 23 * as far as I understood the problem statement. Apparently, this 24 * is not the case. */ 25 int gx = (xp - xq); 26 int gy = (yp - yq); 27 vector<pair<int, int>> v; 28 for (int i = 0; in_range(xp+i*gx, yp+i*gy); i++) 29 v.push_back(make_pair(xp+i*gx, yp+i*gy)); 30 for (int i = 0; in_range(xq-i*gx, yq-i*gy); i++) 31 v.push_back(make_pair(xq-i*gx, yq-i*gy)); 32 return v; 33 } 34 35 void add_antinodes(set<pair<int, int>>& points, 36 pair<int, int> p, set<pair<int, int>>& antinodes) { 37 for (auto q : points) { 38 auto a = antinode_all(p, q); 39 for (auto r : a) 40 antinodes.insert(r); 41 } 42 } 43 44 int main() { 45 string line; 46 map<char, set<pair<int, int>>> d; 47 set<pair<int, int>> antinodes; 48 int i, j; 49 for (i = 0; getline(cin, line); i++) { 50 stringstream s(line); 51 char c; 52 for (j = 0; s >> c; j++) { 53 if (c != '.') { 54 pair<int, int> p(i, j); 55 add_antinodes(d[c], p, antinodes); 56 d[c].insert(p); 57 } 58 } 59 } 60 61 int tot = 0; 62 for (auto [x, y] : antinodes) 63 if (in_range(x, y)) 64 tot++; 65 66 cout << tot << endl; 67 return 0; 68 }