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