結果

問題 No.245 貫け！
ユーザー h_nosonh_noson
提出日時 2016-05-22 22:56:13
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 1 ms
6,816 KB
testcase_05 AC 1 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,816 KB
testcase_08 AC 1 ms
6,820 KB
testcase_09 AC 3 ms
6,820 KB
testcase_10 AC 3 ms
6,820 KB
testcase_11 AC 11 ms
6,820 KB
testcase_12 AC 26 ms
6,816 KB
testcase_13 AC 26 ms
6,820 KB
testcase_14 AC 27 ms
6,816 KB
testcase_15 AC 27 ms
6,816 KB
testcase_16 AC 30 ms
6,816 KB
testcase_17 AC 28 ms
6,816 KB
testcase_18 AC 27 ms
6,820 KB
testcase_19 AC 27 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

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