JOI Open Contest 2012 : Jumps

問題概要

2次元格子上にN(<10^5)個の点がある。線分が交わらないハミルトン路を出力する問題。

解法

x座標でソートしてからx座標最小の1点を中心に角度でソートする。このとき、全てが同一直線上にならんでいるときは解なし。それ以外のときは角度が小さい順に拾っていけばよい。角度が同じ複数の点については距離の遠いところから順に拾っていけばよいけど、角度が最小なときに限り近いところから拾っていくようにする。
ところでこの問題、output validatorどうやってるんだろう…。

acceptされたコード

ビジュアライザでのデバッグは楽しかった。

#include <vector>
#include <cassert>
#include <fstream>
#include <string>
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

typedef long long int64;

struct Point {
	int64 x, y;
	int index;
	Point(){}
	Point(int64 x, int64 y, int index = -1):
		x(x), y(y), index(index)
	{}
};

bool cmpX (const Point& lhs, const Point& rhs) {
	return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y);
}

bool cmpY (const Point& lhs, const Point& rhs) {
	return lhs.y < rhs.y || (lhs.y == rhs.y && lhs.x < rhs.x);
}


template<typename numType>
numType gcd(numType a, numType b) {
	for (;b != 0;) {
		numType t = a % b;
		a = b;
		b = t;
	}
	return a;
}



int64 xx, yy;
bool foundNegaY;
bool foundNegaX;

struct Fraction {
	int64 x, y;
	int index;
	Fraction(){}
	Fraction(int64 x, int64 y, int index = -1):
		x(x), y(y), index(index)
	{}
};

set< pair<int64, int64> > ss;

bool operator< (const Fraction& lhs, const Fraction& rhs) {
	if (rhs.x == 0 && lhs.x == 0) {
		return lhs.y > rhs.y;
	}
	if (lhs.y == 0 && rhs.y == 0) {
		return foundNegaY ^ (lhs.x < rhs.x);
	}
	int64 l = lhs.y * rhs.x, r = lhs.x * rhs.y;
	if (l != r) {
		return l < r;
	}
	else {
		int64 d = gcd(abs(lhs.y), abs(lhs.x));
		pair<int64, int64> p = make_pair(lhs.y / d, lhs.x / d);
		if (yy == p.first && xx == p.second) {
			return lhs.x <  rhs.x;
		}
		else {
			return lhs.x > rhs.x;
		}
	}
}


const int MAX_N = int(1e5);
const int INF = int(1.05e9); 

int N;
int ans[MAX_N];
Point orig[MAX_N];
Point ps[MAX_N];
Fraction fs[MAX_N];

void init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		orig[i] = Point(x, y, i);
	}
}


void solve() {
	for (int i = 0; i < N; ++i) {
		ps[i] = orig[i];
	}
	sort(ps, ps + N, cmpX);
	foundNegaY = false;
	foundNegaX = false;
	for (int i = N - 1 ; i >= 0; --i) {
		ps[i].x -= ps[0].x;
		ps[i].y -= ps[0].y;
		foundNegaY |= ps[i].y < 0;
	}
	xx = 0; yy = 1;
	for (int i = 0; i < N; ++i) {
		fs[i] = Fraction(ps[i].x, ps[i].y, ps[i].index);
		if (i > 0) {
			if (yy * ps[i].x > xx * ps[i].y) {
				yy = ps[i].y;
				xx = ps[i].x;
			}
			if (ps[i].x == 0) {
				ss.insert(make_pair(INF, 0));
			}
			else if (ps[i].y == 0) {
				ss.insert(make_pair(0, 1));
			}
			else {
				int64 d = gcd(abs(ps[i].x), abs(ps[i].y));
				ss.insert(make_pair(ps[i].y / d, ps[i].x / d));
			}
		}
	}
	if (int(ss.size()) == 1) {
		puts("0");
		return ;
	}
	sort(fs+1, fs+N);
	for (int i = 0; i < N; ++i) {
		ans[i] = fs[i].index;
	}
	for (int i = 0; i < N; ++i) {
		printf("%d\n", ans[i] + 1);
	}
}

int main() {
	init();
	solve();
	return 0;
}