SRM 652 Div2 1000 NoRightTurnDiv2

問題概要
二次元座標上にN個の点が与えられる。
このN個の点すべてをある順番に従って訪れたい。以下の条件を満たすように移動するとき、どのような順で点を訪れればよいか求めよ。

• 点から点への移動するときは二点を結ぶ直線上を移動しなければならない
• 移動したパスが交差してはならない
• 右にターンすることはできない（パスは反時計周りにならないといけない）

解法
最も右側の点から始める。最も右側の点が複数個ある場合は、その中で最も下側にあるものを選ぶ。あとは反時計まわりになるように、外側の点からgreedyに訪問すればいい。反時計まわりの判定、最も外側の判定は外積を使って行う。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int vis[50];

long long cross(long long x1, long long y1, long long x2, long long y2) {
  return x1 * y2 - x2 * y1;
}

class NoRightTurnDiv2 {
  public:
  vector<int> findPath(vector<int> x, vector<int> y) {
    memset(vis, 0, sizeof(vis));
    vector<int> ret;
    int n = x.size();
    int p2 = 0;
    FOR (i, 1, n) {
      if (make_pair(x[i], -y[i]) > make_pair(x[p2], -y[p2]))
        p2 = i;
    }
    x.push_back(x[p2]);
    y.push_back(y[p2]-1000);
    vis[p2] = true;
    ret.push_back(p2);
    int p1 = n;
    
    REP (i, n-1) {
      int p3 = -1;
      REP (j, n) {
        if (vis[j])
          continue;
        if (p3 == -1 ||
            (cross(x[p2]-x[p1], x[j]-x[p2], y[p2]-y[p1], y[j]-y[p2]) >= 0 &&
             cross(x[j]-x[p2], x[p3]-x[p2], y[j]-y[p2], y[p3]-y[p2]) >= 0)) {
          p3 = j;
        }
      }
      vis[p3] = true;
      ret.push_back(p3);
      p1 = p2;
      p2 = p3;
    }
    return ret;
  }
};