AOJ 2009 - Area Separation

毎回どうだっけってなる．

解法

1本ずつ直線を足していく．(今までの直線(正方形の辺を含む)と加えた直線の交点)-1だけ領域が増える．但し，正方形内にない交点は含まない．
重複して数えないよう注意する．例えば，

から

のように直線を加えたとき，交点は3つである．

コード

ライブラリの部分は省略しています．

#include <cstdio>
#include <algorithm>

double EPS = 1e-9;

int N;
bool used[25252];
P line[104][2];

int main(){
    line[0][0] = {-100.0, -100.0};
    line[0][1] = {-100.0, 100.0};
    line[1][0] = {-100.0, 100.0};
    line[1][1] = {100.0, 100.0};
    line[2][0] = {100.0, 100.0};
    line[2][1] = {100.0, -100.0};
    line[3][0] = {100.0, -100.0};
    line[3][1] = {-100.0, -100.0};
    
    while(scanf("%d", &N), N){
        for(int i=4;i<N+4;i++){
            double x1, y1, x2, y2;
            scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);

            line[i][0].real(x1);
            line[i][0].imag(y1);
            line[i][1].real(x2);
            line[i][1].imag(y2);
        }

        std::vector<P> v{{-100, -100}, {-100, 100}, {100, 100}, {100, -100}};
        int res = 1;
        for(int i=4;i<N+4;i++){
            for(int j=0;j<25252;j++){used[j] = false;}
            
            for(int j=0;j<i;j++){
                if(areIntersectedLines(line[i][0], line[i][1], line[j][0], line[j][1])){
                    P p = intersection(line[i][0], line[i][1], line[j][0], line[j][1]);
                    double x = real(p), y = imag(p);
                    if(x < -100.0 - EPS || x > 100.0 + EPS || y < -100.0 - EPS || y > 100.0 + EPS){continue;}

                    bool f = true;
                    for(int k=0;k<v.size();k++){
                        if(std::abs(dist(p-v[k])) < 1e-10){
                            if(!used[k]){used[k] = true; res++;}
                            f = false;
                            break;
                        }
                    }
                    if(f){res++; v.push_back(p);}
                }
            }
            res--;
        }

        printf("%d\n", res);
    }