SRM 239 DIV1 Hard HiddenTriangles

SRM 実装のアイデア

問題 Editorial

問題

座標軸に平行か45°斜めかのどちらかの線分が複数与えられる。
この中作ることができる三角形を数えろ

  • 0 <= 線分の数 <= 50
  • 線分はオーバーラップすることもある

解答

まず、重複しないように辺をマージする。
次に、線分同士で交差する点を全部列挙する。
斜めは45°なので、最初に座標を2倍すれば交差する点は整数座標で表せる。
任意の辺で繋がった2点を考えると、辺の向きによってちょうど2つの可能な三角形がわかる。
それをチェックして数える

コメント

ぐちゃぐちゃになってしまった。
何時間もかかってるし一回セグフォで落ちてるし…
もっと普通にできたい

コード

#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#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 all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))

using namespace std;
typedef vector<int> vi; typedef long long ll;

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) {}
};

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 bool operator==(const P& a, const P& b) { return a.x == b.x && a.y == b.y; }
inline bool operator<(const P& a, const P& b) { return a.x < b.x || (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 norm(const P& a) { return (P::T2)a.x*a.x + (P::T2)a.y*a.y; }
inline P operator*(P::T a, const P& b) { return P(a * b.x, a * b.y); }
inline P operator/(const P& a, P::T b) { return P(a.x / b, a.y / b); }

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;
}
P crosspoint(const L &l, const L &m) {
	P::T2 A = cross(l[1] - l[0], m[1] - m[0]);
	P::T2 B = cross(l[1] - l[0], l[1] - m[0]);
	if(A == 0 && B == 0) return m[0];
	return m[0] + B * (m[1] - m[0]) / A;
}
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 4;	// 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 3;	//segment overlap
	else return 1;
}

struct HiddenTriangles {
	int dir(L l) {
		P p = l.b - l.a;
		return p.x == 0 ? 0 : p.y == 0 ? 1 : (P::T2)p.x * p.y > 0 ? 2 : 3;
	}
	static inline int coordinateIndex(int x, int y) {
		return (x + 450) * 900 + (y + 450);
	}
	int howMany(vector <int> X1, vector <int> Y1, vector <int> X2, vector <int> Y2) {
		int n = X1.size();
		vector<L> ls;
		rep(i, n) ls.pb(L(2 * P(X1[i], Y1[i]), 2 * P(X2[i], Y2[i])));
		static bool dupl[50];
		mset(dupl, 0);
		rep(i, n) reu(j, i+1, n) if(!dupl[j] && intersectSS(ls[i], ls[j]) >= 3 && dir(ls[i]) == dir(ls[j])) {
			L l = L(min(min(ls[i].a, ls[i].b), min(ls[j].a, ls[j].b)), max(max(ls[i].a, ls[i].b), max(ls[j].a, ls[j].b)));
			ls[i] = l;
			dupl[j] = true;
			--i; break;
		}
		{ vector<L> nls; rep(i, n) if(!dupl[i]) nls.pb(ls[i]); ls.swap(nls); n = ls.size(); }
		vector<P> ps;
		rep(i, n) {
			ps.pb(ls[i].a), ps.pb(ls[i].b);
		}
		rep(i, n) reu(j, i+1, n) {
			int c = intersectSS(ls[i], ls[j]);
			if(c == 0 || c == 2) {
				P p = crosspoint(ls[i], ls[j]);
				ps.pb(p);
			}
		}
		sort(all(ps)); ps.erase(unique(all(ps)), ps.end());
		int m = ps.size();
		static int index[1000*1000];
		mset(index, -1);
		rep(i, m) index[coordinateIndex(ps[i].x, ps[i].y)] = i;
		int count = 0;
		vector<vi> ts(n);
		static bool edge[1500][1500];
		mset(edge, 0);
		rep(i, n) {
			rep(j, m) if(ccw(ls[i].a, ls[i].b, ps[j]) == 0) ts[i].pb(j);
			each(j, ts[i]) each(k, ts[i]) edge[*j][*k] = true;
		}
		rep(i, n) {
			const vi& t = ts[i];
			int d = dir(ls[i]);
			rep(p1, t.size()) { int px = ps[t[p1]].x, py = ps[t[p1]].y; reu(p2, p1+1, t.size()) {
				int qx = ps[t[p2]].x, qy = ps[t[p2]].y;
				#define CHECK(x, y) {\
					int k = index[coordinateIndex(x, y)];\
					if(k != -1 && edge[t[p1]][k] && edge[t[p2]][k])\
						count ++;\
					}
				switch(d) {
				case 0:
					if((qy - py) % 2 == 0) {
						CHECK(px + (qy - py) / 2, (qy + py) / 2);
						CHECK(px - (qy - py) / 2, (qy + py) / 2);
					}
					break;
				case 1:
					if((qx - px) % 2 == 0) {
						CHECK((qx + px) / 2, py + (qx - px) / 2);
						CHECK((qx + px) / 2, py - (qx - px) / 2);
					}
					break;
				case 2:
				case 3:
					CHECK(px, qy);
					CHECK(qx, py);
					break;
				}
			} }
		}
		return count;
	}
};