Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2007-day4 lines

問題文 : 直線

解法 :

オイラーの多面体定理です.

"V(頂点数) - E(辺数) + F(面数) = D(次元) - 1"

が成立するので, D=2から, F = E + 1 - V が求まります.
EだったりV だったりは入力から簡単にもとまるので, 愚直に計算しても O(N^2 log N) で解を得ることが出来ます. (がんばればlog は消えるかもしれません.

コード :

#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

typedef pair<int, int> P;
typedef pair<P, int> T;
typedef pair<P, P> D;

int main()
{
	set<T> s;
	set<D> p, mc;
	int N;
	int a, b, c, d;
	
	scanf("%d", &N);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d %d %d", &a, &b, &c, &d);
		
		int sign = 1;
		int D = __gcd(abs(b - d), __gcd(abs(c - a), abs(a * d - b * c)));
		if (b - d < 0) sign = -1;
		s.insert(make_pair(make_pair(sign * (b - d) / D, sign * (c - a) / D), sign * (a * d - b * c) / D));
	}
	
	set<T>::iterator it1, it2;
	
	int ct = 0;
	for (it1 = s.begin(); it1 != s.end(); it1++){
		mc.clear();
		for (it2 = s.begin(); it2 != s.end(); it2++){
			int sign = 1;
			int D = (*it1).first.first * (*it2).first.second - (*it1).first.second * (*it2).first.first;
			if (D < 0) sign = -1;
			if (D != 0){
				int A = -(*it2).first.second * (*it1).second + (*it1).first.second * (*it2).second;
				int B = (*it2).first.first * (*it1).second - (*it1).first.first * (*it2).second;
				int D1 = __gcd(abs(A), abs(D)), D2 = __gcd(abs(B), abs(D));
				p.insert(make_pair(make_pair(A / D1 * sign, D / D1 * sign), make_pair(B / D2 * sign, D / D2 * sign)));
				mc.insert(make_pair(make_pair(A / D1 * sign, D / D1 * sign), make_pair(B / D2 * sign, D / D2 * sign)));
			}
		}
		ct += mc.size();
	}
	
	printf("%d\n", 1 - p.size() + s.size() + ct);
	
	return (0);
}