結果

問題 No.245 貫け！
コンテスト
ユーザー mayoko_
提出日時 2015-07-22 07:46:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 64 ms / 5,000 ms
コード長 3,215 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 711 ms
コンパイル使用メモリ 88,788 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-08 11:45:18
合計ジャッジ時間 1,795 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

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