SRM 225 DIV1 Hard Triangulation

問題 Editorial

問題

(凸とは限らない)単純多角形の三角形分割を、辞書順最小でしろ。
引かれた対角線と多角形は、始点・終点以外で交差や触れてはならない

解答

まず、適当に対角線をひいても、三角形分割ができなくなることはない。つまり単純な辞書順greedyでおｋ。
あとは適当に「既に引いた対角線と交差せず」「多角形自身と交差せず」「多角形の内側にある」かどうかを判定したい。
これは整数幾何でがんばる

コメント

コードのコメントのとおり、「多角形の内側にある」判定で適当なことをしているが、Practice Roomのrng_58さんの解答では面積に着目しているようだ。

コード

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(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)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
using namespace std;
typedef vector<pair<int,int> > vpii; typedef long long ll; typedef vector<string> vs;
struct P {
	typedef int T; typedef ll T2;	//T2は{a*b | a:T, b:T}を含むタイプ
	T x, y;
	P(T x_, T y_): x(x_), y(y_) {}
	P(): x(0), y(0) {}
};
inline bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
inline P operator+(const P& a, const P& b) { return P(a.x+b.x, a.y+b.y); }
inline P operator-(const P& a, const P& b) { return P(a.x-b.x, a.y-b.y); }
inline P::T2 cross(const P& a, const P& b) { return (P::T2)a.x*b.y - (P::T2)a.y*b.x; }
inline P::T2 dot(const P& a, const P& b) { return (P::T2)a.x*b.x + (P::T2)a.y*b.y; }
struct L {
	P a, b;
	L(const P &a_, const P &b_): a(a_), b(b_) {}
	const P& operator[](size_t i) const { return i ? b : a; }
};

inline int ccw(const P& a, const P& b, const P& c) {
	int ax = b.x - a.x, ay = b.y - a.y, bx = c.x - a.x, by = c.y - a.y;
	P::T2 t = (P::T2)ax*by - (P::T2)ay*bx;
	if (t > 0) return 1;
	if (t < 0) return -1;
	if((P::T2)ax*bx + (P::T2)ay*by < 0) return +2;
	if((P::T2)ax*ax + (P::T2)ay*ay < (P::T2)bx*bx + (P::T2)by*by) return -2;
	return 0;
}

int intersectSS(const L &s, const L &t) {
	int a = ccw(s.a,s.b,t.a), b = ccw(s.a,s.b,t.b), c = ccw(t.a,t.b,s.a), d = ccw(t.a,t.b,s.b);
	int x = a * b, y = c * d;
	if(x == -1 && y == -1) return 0;	// cross
	else if(
		((abs(b) == 1 || b == -2) && s.b == t.a) ||
		((abs(b) == 1 || b ==  2) && s.a == t.a) ||
		((abs(a) == 1 || a == -2) && s.b == t.b) ||
		((abs(a) == 1 || a ==  2) && s.a == t.b)
		) return 2;	// point overlap
	else if(
		(x == 0 && (abs(a) + abs(b) == 1)) ||
		(y == 0 && (abs(c) + abs(d) == 1))
		) return 2;	// point overlap
	else if(x <= 0 && y <= 0) return 0;	//line overlap
	else return 1;
}

bool contains(const vector<P>& o, const P& p) {
	bool in = false;
	for (int i = 0; i < o.size(); ++i) {
		P a = o[i] - p, b = o[(i+1)%o.size()] - p;
		if (a.y > b.y) swap(a, b);
		if (a.y <= 0 && 0 < b.y)
			if (cross(a, b) < 0) in = !in;
		if (cross(a, b) == 0 && dot(a, b) <= 0) return true;	//point on edge
	}
	return in;
}

struct Triangulation {
	vector <string> triangulate(vector <int> x, vector <int> y) {
		int n = x.size();
		vector<P> p, p2;
		rep(i, n) p.pb(P(x[i], y[i])), p2.pb(p[i] + p[i]);
		vector<L> lines, pl;
		rep(i, n) pl.pb(L(p[i], p[(i+1)%n]));
		vpii v;
		//greedyにやる
		rep(ii, n-3) {
			rep(j, n) reu(k, j+1, n) {
				L s = L(p[j], p[k]);
				bool b = true;
				int pcount = 0;
				rep(l, n) {
					int c = intersectSS(pl[l], s);
					b &= c != 0;
					if(c == 2) pcount ++;
				}
				each(l, lines) b &= intersectSS(*l, s) != 0;
				//多角形の内側に線分があるかどうか。
				//多角形と交差していないなら、線分の適当な場所の点が多角形の内側にあるか見ればいい。
				//ここではちょうど半分の点でやっている。整数でやるために多角形も2倍
				b &= contains(p2, s[0] + s[1]);
				//始点と終点の周囲以外で触れてたら駄目
				b &= pcount == 4;
				if(b) {
					lines.pb(s);
					v.pb(mp(j, k));
					goto next;
				}
			}
			next:;
		}
		vs r;
		each(i, v) {
			stringstream ss;
			ss << i->first << " " << i->second;
			r.pb(ss.str());
		}
		return r;
	}
};