SRM 206 DIV1 Hard HexagonIntersections

問題 Editorial

問題

HexMapがあって、座標が2つ与えられる。
その点と点を結ぶ線分と交差する6角形の数を答えよ。
ただしエッジの上にオーバーラップする場合や、角の1点だけで触れる場合はカウントしない

• • 10000 <= x0, y0, x1, y1 <= 10000

解答

Editorialを読んだ。
まず、座標を斜めに変換する(Editorialの図を参照)。こうすることによって座標が整数で扱えるようになる。
この変換では2点を結ぶ線分の交差状況が保存されることに注意。
あとは適当に当たりそうな六角形を列挙し、エッジと交差判定をしてやればいい

コメント

座標の変換はいいね！わりと感動した。
座標を変換する時は、保存させたい事を考える。
幾何はこういうことで簡単になることが多いし、考え方を身につけていこう。
他の人のコードを読んだら、六角形との判定で、自分のやり方でなく、「ひとつでもエッジ・対角線と交差したら交差」というやり方があった。なるほど。これなら小数でも、誤差のある「上に乗ってるだけのやつ4つ」の部分がなくなるから誤差に強くなるなあ

コード

#include <vector>
#include <set>
#include <iostream>
#include <ctime>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
using namespace std;
typedef long long ll;

struct P {
	typedef int T; typedef ll T2;	//T2は{a^2 | a:T}を耐えられるタイプ
	T x, y;
	P(T x_, T y_): x(x_), y(y_) {}
	P(): x(0), y(0) {}
	operator complex<double>() { return complex<double>(x, y); }
};
bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
bool operator<(const P& a, const P& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); }
P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); }
P operator-=(P& a, const P& b) { a.x -= b.x, a.y -= b.y ; return a; }
P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; }
P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; }
P::T2 norm(const P& a) { return (P::T2)a.x*a.x + (P::T2)a.y*a.y; }
ostream& operator<<(ostream& out, const P& x) { out << "(" << x.x << ", " << x.y << ")"; return out; }

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

int ccw(P a, P b, P c) {
  b -= a, c -= a;
  P::T2 t = cross(b, c);
  if (t > 0) return 1;
  if (t < 0) return -1;
  if(dot(b, c) < 0) return +2;
  if(norm(b) < norm(c)) return -2;
  return 0;
}

int intersectSS(const L &s, const L &t) {
	int x = ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]), y = ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]);
	if(x == -1 && y == -1) return 2;
	else if(x <= 0 && y <= 0) return 1;
	else return 0;
}

typedef complex<double> PD;

struct HexagonIntersections {
	P toEuclidean(P p) {
		return P(p.x + p.y, 2*p.y - p.x);
	}
	P fromEuclidean(P p) {
		return P((2 * p.x - p.y) / 3, (p.x + p.y) / 3);
	}
	int count(int x0, int y0, int x1, int y1) {
		P p0 = toEuclidean(P(x0, y0)), p1 = toEuclidean(P(x1, y1));
		double ang = arg((PD)(p1 - p0)), dist = abs((PD)(p1 - p0));
		set<P> se;
		PD cd = PD(cos(ang), sin(ang));
		//適当に当たりそうな所をとってくる
		for(double i = 0; i <= dist; i += .5) {
			PD c = (PD)p0 + i * cd;
			P a = fromEuclidean(P((int)(real(c)+.5), (int)(imag(c)+.5)));
			int x = a.x, y = a.y;
			rer(dx, -1, 1) rer(dy, -1, 1) {
				se.insert(P(x+dx, y+dy));
			}
		}
		int s = 0;
		L l = L(p0, p1);
		each(i, se) {
			P p = toEuclidean(*i);
			static P a[6];
			a[0] = p + P(   0,  1);
			a[1] = p + P(   1,  1);
			a[2] = p + P(   1,  0);
			a[3] = p + P(   0, -1);
			a[4] = p + P(  -1, -1);
			a[5] = p + P(  -1,  0);
			bool b = *i == P(x0, y0) || *i == P(x1, y1);
			int x = 0;
			rep(j, 6) {
				int t = intersectSS(l, L(a[j], a[(j+1)%6]));
				b |= t == 2;
				x += t == 1;
			}
			//厳密に交差しているものが一つでもある、もしくは、上に乗ってるやつが4つある場合に六角形と交差してる
			if(b || x >= 4) {
				s ++;
			}
		}
		return s;
	}
};
#undef double