UVa979 The Abominable Triangleman

UVa

問題
http://uva.onlinejudge.org/external/9/979.html

意訳
伝説の三角形 MGT が忌まわしき略奪者トライアングルマンによって平面世界に隠されてしまった。三角形は自由に回転、平行、反転がなされている可能性があり、加えて無慈悲にも多数の点の上に紛れている。もとの三角形の頂点情報が入力で与えられるので、紛れてしまった伝説の三角形の頂点を出力せよ。

制約

  • 4 <= N <= 2000

解法

頂点を３重ループしたら間に合わない。誤差を気にしないで間に合う解法を考える。

入力の頂点の集合から辺の集合を作る。ここから更に、入力の三角形の３辺と同じ長さの辺のみを取り出す。この辺の集合を長さでソートすると二分探索により、元の三角形の各辺に対応する可能性のある辺の集合 Sa, Sb, Sc が求まる。それぞれの集合の要素数はかなり限定されているので、集合 Sa, Sb, Sc から辺を取り出して３重ループすることができる。

しかし、まだそれぞれの集合から取り出した辺 Ea_i, Eb_j, Ec_k が三角形を成すかどうかの判定をする必要が残っている。

これは入力の時点で、与えられた全ての点を判別できるようにナンバリングしておくと解決する。
辺 Ea_i, Eb_j, Ec_k それぞれが所持する頂点の番号が 2 回ずつ使われていたら、これらの辺は三角形を成すことが分かる。

#include <bits/stdc++.h>

using namespace std;

#define pow2(x) ((x)*(x))
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define rep(i,n) REP(i,0,n)
#define ALL(c) (c).begin(), (c).end()

struct Point {
  int x, y, idx;
};

typedef pair<int,int> P;

bool operator < (const Point &lhs, const Point &rhs) { lhs.idx < rhs.idx; }

struct Edge {
  Point p1, p2;
  
  int norm() const {
    return int( pow2(p1.x-p2.x) + pow2(p1.y-p2.y) );
  }
};

bool operator < (const Edge &lhs, const Edge &rhs) { return lhs.norm() < rhs.norm(); }

typedef vector<Edge>::const_iterator Iter;

int main() {
  
  bool blank = false;
  
  while(1) {
    Point oriPs[3];
    
    rep(i, 3) {
      if( !(cin >> oriPs[i].x >> oriPs[i].y) ) return 0;
      oriPs[i].idx = -1;
    }
    
    vector<Edge> oriEs;
    rep(i, 3)
      oriEs.push_back( (Edge){oriPs[i], oriPs[(i+1)%3]} );
    sort(ALL(oriEs));
    
    int N; cin >> N;
    vector<Point> ps(N);
    rep(i, N) {
      cin >> ps[i].x >> ps[i].y;
      ps[i].idx = i;
    }
    
    vector<Edge> es;
    rep(i, N-1)
      REP(j, i+1, N)
        es.push_back( (Edge){ps[i], ps[j]} );
    sort(ALL(es));
    
    vector<pair<Iter, Iter> > iters;
    rep(i, 3) {
      iters.push_back( make_pair( lower_bound(ALL(es), oriEs[i]),
                                  upper_bound(ALL(es), oriEs[i])
                                  ));
    }
    
    vector<P> ans;
    for(Iter it0 = iters[0].first; it0 != iters[0].second; it0++) {
      for(Iter it1 = iters[1].first; it1 != iters[1].second; it1++) {
        for(Iter it2 = iters[2].first; it2 != iters[2].second; it2++) {
          map<int, int> mp;
          mp[it0->p1.idx] ++; mp[it0->p2.idx] ++;
          mp[it1->p1.idx] ++; mp[it1->p2.idx] ++;
          mp[it2->p1.idx] ++; mp[it2->p2.idx] ++;
          
          bool ok = true;
          for(map<int,int>::const_iterator itm=mp.begin(); itm!=mp.end(); itm++) {
            ok = ok && (itm->second == 2);
          }
          
          if(ok) {
            set<P> st;
            st.insert(P(it0->p1.x, it0->p1.y));
            st.insert(P(it1->p1.x, it1->p1.y));
            st.insert(P(it2->p1.x, it2->p1.y));
            
            st.insert(P(it0->p2.x, it0->p2.y));
            st.insert(P(it1->p2.x, it1->p2.y));
            st.insert(P(it2->p2.x, it2->p2.y));
            for(set<P>::const_iterator its=st.begin(); its!=st.end(); its++) {
              ans.push_back(*its);
            }
            goto EXIT;
          }
        }
      }
    }
    
  EXIT:;
    
    if(blank) cout << endl;
    blank = true;
    
    for(int i=0; i<ans.size(); i++) {
      cout << ans[i].first << ' ' << ans[i].second << endl;
    }
    
  }
  
  return 0;
}