5588 별자리 찾기

다 해보면 된다.

찾고싶은 별자리를 pair<int,int> s 배열에 저장하고 m개의 별을 set에 저장해 준 후

1<=i<=m 일 때 i번째 별을 찾고싶은 별자리의 첫번째 별로 간주했을 때 차이를 dif에 저장해놓고

s배열의 모든 요소 + dif가 set에 모두 있다면 -dif를 출력한다.

u,d,l,r은 찾고싶은 별자리가 s[0]를 기준으로 사방으로 얼만큼 더 뻗느냐를 저장해놓고

그정도 여유공간이 없는 별은 첫번째 별 후보에서 제외시켰는데 속도차이를 느끼지 못했다.

<코드>

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> pii;
 
#define mv 1000000
 
struct star {
    int x, y;
    star(int x = 0, int y = 0) : x(x), y(y) {}
    star operator-(const star& a) {
        return{ x - a.x,y - a.y };
    }
};
 
star s[201];
vector<star> s2, s3;
 
set<int> m[mv + 1];
 
int n, nn, u, d, l, r;
 
int main() {
    scanf("%d", &n);
    d = l = mv + 1;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &s[i].x, &s[i].y);
        u = max(u, s[i].x);
        d = min(d, s[i].x);
        l = min(l, s[i].y);
        r = max(r, s[i].y);
    }
    u -= s[0].x;
    d = s[0].x - d;
    l = s[0].y - l;
    r -= s[0].y;
    scanf("%d", &nn);
    for (int i = 0; i < nn; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a + u <= mv && a - d >= 0 && b + r <= mv && b - l >= 0) s2.push_back({ a,b });
        m[a].insert(b);
    }
    star dif, nx;
    bool f = true;
    for (int i = 0; i < s2.size() && f; i++) {
        dif = s[0] - s2[i]; // -2,3
        for (int j = 1; j < n && f; j++) {
            nx = s[j] - dif;
            if (!m[nx.x].count(nx.y)) f = false;
        }
        if (f) {
            printf("%d %d", -dif.x, -dif.y);
            break;
        }
        f = true;
    }
    return 0;
}