yukicoder No.245 貫け！

幾何ライブラリを補充しました。

問題

No.245 貫け！ - yukicoder

解法

「どの端点とどの端点を通るような直線を作るか」で全探索する。

直線が線分と交差しているかどうかの判定は基本的には蟻本に書いてあるとおり。ただサンプル4のようなケースは通らないので,

直線と線分が平行かどうか判定->平行な場合,2つの直線の距離が0かどうか判定

という流れを追加しました。

double eps = 1e-8;

double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

struct P {
    double x, y;
    P() {}
    P(double x, double y) : x(x), y(y) {}
    P operator+(P p) const {return P(add(x, p.x), add(y, p.y));}
    P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));}
    P operator*(double d) const {return P(x*d, y*d);}
    double dot(P p) const {return add(x*p.x, y*p.y);} // 内積
    double det(P p) const {return add(x*p.y, -y*p.x);} // 外積
    double dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離
    void normalize() {double d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化
    bool operator<(const P& rhs) const {
        if (x != rhs.x) return x < rhs.x;
        return y < rhs.y;
    }
    bool operator==(const P& rhs) const {
        return equal(x, rhs.x) && equal(y, rhs.y);
    }
};

// 線分p1-p2上に点qがあるかを判定する
bool on_seg(P p1, P p2, P q) {
    return (p1-q).det(p2-q) == 0 && (p1-q).dot(p2-q) <= 0;
}

// 直線p1-p2と直線q1-q2が平行かどうかの判定
bool parallel(P p1, P p2, P q1, P q2) {
    P a = p2-p1;
    P b = q2-q1;
    return a.det(b) == 0;
}

// 直線p1-p2と直線q1-q2が平行な場合の,2つの直線の距離
double dist(P p1, P p2, P q1, P q2) {
    P p = p2-p1;
    p = P(-p.y, p.x);
    p.normalize();
    return abs(p.dot(p1-q1));
}

// 直線p1-p2と直線q1-q2の交点
P intersection(P p1, P p2, P q1, P q2) {
    return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
}

const int MAXN = 111;
int N;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
P Pt[MAXN][2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        Pt[i][0] = P(A[i], B[i]);
        Pt[i][1] = P(C[i], D[i]);
    }
    int ans = 1;
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            for (int k = 0; k < 2; k++) for (int l = 0; l < 2; l++) {
                int cnt = 0;
                for (int m = 0; m < N; m++) {
                    if (parallel(Pt[i][k], Pt[j][l], Pt[m][0], Pt[m][1])) {
                        if (dist(Pt[i][k], Pt[j][l], Pt[m][0], Pt[m][1]) == 0) cnt++;
                    } else {
                        P t = intersection(Pt[i][k], Pt[j][l], Pt[m][0], Pt[m][1]);
                        if (on_seg(Pt[m][0], Pt[m][1], t)) cnt++;
                    }
                }
                ans = max(ans, cnt);
            }
        }
    }
    cout << ans << endl;
    return 0;
}