0524:Searching Constellation

与えられた点と同じ形を点の集合の中から探し、
平行移動する量を出力する問題。

二分探索で一つずつ探した。

#include<iostream>
#include<vector>
#include<set>
#include<climits>
#include<cfloat>
#include<cmath>
#include<algorithm>
 
 
using namespace std;
 
double EPS = 1e-10;
 
 
double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}
 
struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}
 
  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }
 
  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }
 
  bool operator == ( const point &p ) const {
    return abs(x-p.x) < EPS && abs(y-p.y) < EPS;
  }
};
 
bool cmp_x(const point& p, const point& q){
  if(p.x != q.x)return p.x<q.x;
  return p.y < q.y;
}
 

vector<point>N;

bool Binary_search(point x){
  int l=0,r=N.size(),mid=(l+r)/2;
 
  while(r-l>1){
    if(N[mid]==x)return true;
 
    if(x.x < N[mid].x ||(N[mid].x==x.x && x.y < N[mid].y))r=mid;
    else l=mid;
 
    mid=(l+r)/2;
  }
 
  if(N[mid]==x)return true;
  return false;
}
 
point solve(vector<point> M){
 
  for(int i=0; i< N.size(); i++){
    int j=1;
    for(; j< M.size(); j++){
      point t=N[i]+M[j]-M[0];
      if(!Binary_search(t))break;  
    }
    if(j==M.size())return N[i]-M[0];
  }
  return M[0];
}
 
int main(void){
  int n,m;
  point in;
  vector<point>M;
 
  while(cin >> m,m){
    M.clear();
    N.clear();   
 
    for(int i=0; i< m; i++){
      cin >> in.x >> in.y;
      M.push_back(in);
    }
     
    cin >> n;
 
    for(int i=0; i< n; i++){
      cin >> in.x >> in.y;
      N.push_back(in);
    }
 
    sort(N.begin(),N.end(),cmp_x);
 
    point res=solve(M);
 
    cout << res.x <<" "<< res.y << endl;
 
  }
 
  return 0;
}