[BOJ]5588 별자리 찾기

문제 링크



풀이

기준으로 주어진 별의 무리 전체를 모두 평행이동 시켜보면서 완전히 겹치는게 있는지 보면 된다. 
주어진 별의 개수가 많지 않아서 이런식으로 풀면 됨.
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<intint>> vc(m);
    for (int i = 0; i < m; i++) {
        cin >> vc[i].first >> vc[i].second;
        
    }
    int n;
    cin >> n;
    vector<pair<intint>>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<intint> 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


이미지 맵

BOJ 다른 글

이전 글

다음 글