AOJ2009 Area Separation

問題ページ
Area Separation | Aizu Online Judge

考えたこと

• ある線を引く時、既に引いている線分との(交点の数+1)個領域が増える
• ただし一つの交点に3本以上の線分が交差している場合、重複して数えてはいけない
• 正方形の辺上で交わる場合を交差に数えてはいけないのを抜かしていて時間を溶かした

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

const double EPS = 1e-10;

using R = long double;
using P = complex<R>;
using L = pair<P,P>;
struct S : public L {
  S() {}
  S(const P &a, const P &b) : L(a,b) {}
};

inline int sgn(const R& r) { return (r>EPS) - (r<-EPS); }
inline R det(const P& a, const P& b) {
  return real(a)*imag(b) - imag(a)*real(b);
}
inline P vec(const L& l) {return l.second - l.first;}
namespace std {
    bool operator < (const P& a, const P& b) {
        return sgn(real(a-b)) ? real(a-b) < 0 : sgn(imag(a-b)) < 0;
    }
    bool operator == (const P& a, const P& b) {
        return sgn(real(a-b)) == 0 && sgn(imag(a-b)) == 0;
    }
}

// P,L,Sについて入力
inline istream& operator>>(istream& is, P& p) {
  R x, y;
  is >> x >> y;
  p = P(x, y);
  return is;
}
inline istream& operator>>(istream& is, L& l) {
  P a, b;
  is >> a >> b;
  l = L(a, b);
  return is;
}
inline istream& operator>>(istream& is, S& s) {
  P a, b;
  is >> a >> b;
  s = S(a, b);
  return is;
}

enum CCW{LEFT=1, RIGHT=2, BACK=4, FRONT=8, ON_SEG=16};
int ccw(P a, P b, P c) {
    P p = (c-a)/(b-a);
    if(sgn(imag(p)) > 0) return LEFT;
    if(sgn(imag(p)) < 0) return RIGHT;
    if(sgn(real(p)) < 0) return BACK;
    if(sgn(real(p)-1) > 0) return FRONT;
    return ON_SEG;
}

template<bool strict=false> inline bool intersect(const S&s1, const S&s2) {
  int ccw1 = ccw(s1.first, s1.second, s2.first) | ccw(s1.first, s1.second, s2.second);
  int ccw2 = ccw(s2.first, s2.second, s1.first) | ccw(s2.first, s2.second, s1.second);
  if(strict) return (ccw1 & ccw2) == (LEFT | RIGHT);
  return (ccw1 & ccw2) == (LEFT | RIGHT) || ((ccw1 | ccw2) & ON_SEG);
}

inline P crosspoint(const L& l1, const L& l2) {
  R ratio = det(vec(l2), l2.first-l1.first)/det(vec(l2),vec(l1));
  return l1.first + vec(l1)*ratio;
}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    S s[105];
    REP(i, n) cin >> s[i];

    int ret = 2;
    FOR(i, 1, n) {
      vector<P> v;
      int tmp = 0;
      REP(j, i) {
        if(!intersect<true>(s[i], s[j])) continue;
        P c = crosspoint(s[i], s[j]);
        bool flag = true;
        for(auto k: v) {
          if(k == c) {
            flag = false;
            break;
          }
        }
        if(flag) {
          v.PB(c);
          tmp++;
        }
      }
      ret += tmp + 1;
    }

    cout << ret << endl;
  }

  return 0;
}