ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2009 Area Separation

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2009

正方形領域があり、そこに何本かの直線を引きます。
そのとき領域が何個に分断されるかを求める問題です。


・解法
領域が何個できるかというのは以下のように求めることができます。
i番目の直線を引く時に、i-1番目までに引いた直線との交点を求めます。
⇒ その交点の数+1 個分の領域が増えます。

しかし交点について2つ注意すべきことがあります。
まずは問題文にも書いてありますが、距離が10^-10未満の2点は一致するものとみなしてよいです。
もうひとつ、これはとても重要なのですが交点が正方形の辺上にあるときは交点にカウントしてはいけません。


ソースコード
ライブラリは省略

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cassert>
#include<cstring>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i,0,n)
 
static const int INF = (1 << 29);
static const double EPS = 1e-10;
static const double PI = acos(-1.0);
typedef complex<double> Point;
 
struct Segment{
  Point p1,p2;
  Segment(){}
  Segment(Point p1, Point p2):p1(p1),p2(p2){}
};
 
int n;
Segment segment[100];
 
int solve(){
  int ans = 1;
  for(int i = 0 ; i < n ; i++){
    vector<Point> ps;
    for(int j = 0 ; j < i ; j++){
      Point tmp = getCrossPoint(segment[i],segment[j]);
      if(tmp==Point(INF,INF)) continue;
      if(tmp==segment[i].p1 || tmp==segment[i].p2) continue;
      if(tmp==segment[j].p1 || tmp==segment[j].p2) continue;
      bool check = true;
      for(int k = 0 ; k < ps.size() && check ; k++){
        if(abs(ps[k]-tmp) < EPS) check = false;
      }
      if(check) ps.push_back(tmp);
    }
    ans += ps.size() + 1;
  }
  return ans;
}
 
int main(){
  while(cin >> n, n){
    rep(i,n){
      int x1,y1,x2,y2;
      cin >> x1 >> y1 >> x2 >> y2;
      segment[i] = Segment(Point(x1,y1),Point(x2,y2));
    }
    cout << solve() << endl;
  }
  return 0;
}