結果

問題 No.245 貫け！
ユーザー h_noson
提出日時 2016-05-22 22:56:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 30 ms / 5,000 ms
コード長 1,418 bytes
コンパイル時間 592 ms
コンパイル使用メモリ 57,228 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-06 23:50:26
合計ジャッジ時間 1,355 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define ESP 1e-8

typedef pair<double,double> P;

double det(const P& p, const P& q) {
    return p.first * q.second - p.second * q.first;
}

double dot(const P& p, const P& q) {
    return p.first * q.first + p.second * q.second;
}

P operator+(P p, const P& q) {
    p.first += q.first;
    p.second += q.second;
    return p;
}

P operator-(P p, const P& q) {
    p.first -= q.first;
    p.second -= q.second;
    return p;
}

P operator*(double s, P p) {
    p.first *= s;
    p.second *= s;
    return p;
}

int main(void) {
    int i, j, k, ib, jb, n, ans;
    P x[100][2];
    cin >> n;
    rep (i,n) cin >> x[i][0].first >> x[i][0].second >> x[i][1].first >> x[i][1].second;
    ans = 0;
    rep (i,n) rep (j,n) rep (ib,2) rep (jb,2) if (x[i][ib] != x[j][jb]) {
        int cnt = 0;
        rep (k,n) {
            double a = det(x[i][ib] - x[j][jb],x[i][ib] - x[k][1]);
            double b = det(x[i][ib] - x[j][jb],x[k][0] - x[k][1]);
            if (b*b < ESP) {
                if (a*a < ESP)
                    cnt++;
            }
            else {
                P p = x[k][1] + a / b * (x[k][0] - x[k][1]);
                if (dot(x[k][0] - p,x[k][1] - p) < ESP)
                    cnt++;
            }
        }
        ans = max(cnt,ans);
    }
    cout << ans << endl;
}
0