풀이
기준으로 주어진 별의 무리 전체를 모두 평행이동 시켜보면서 완전히 겹치는게 있는지 보면 된다.
주어진 별의 개수가 많지 않아서 이런식으로 풀면 됨.
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 | #include <iostream> #include <vector> #include <set> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int m; cin >> m; vector<pair<int, int>> vc(m); for (int i = 0; i < m; i++) { cin >> vc[i].first >> vc[i].second; } int n; cin >> n; vector<pair<int, int>>p(n); for (auto &it : p) cin >> it.first >> it.second; sort(vc.begin(), vc.end()); sort(p.begin(), p.end()); int startx = vc[0].first; int starty = vc[0].second; for (int i = 0; i < n; i++) { int diffx = p[i].first - startx; int diffy = p[i].second - starty; for (int j = 0; j < m; j++) { vc[j].first += diffx; vc[j].second += diffy; } int ans = 0; for (int j = 0; j < m; j++) { pair<int, int> q = { vc[j].first,vc[j].second }; for (int i = 0; i < n; i++) { if (q == p[i]) ans++; } } for (int j = 0; j < m; j++) { vc[j].first -= diffx; vc[j].second -= diffy; } if (ans == m) { cout << diffx <<' '<< diffy; break; } } return 0; } | cs |
댓글