結果

問題 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
コンパイル時間 589 ms
コンパイル使用メモリ 57,964 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-16 08:30:51
合計ジャッジ時間 1,543 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 12 ms
5,376 KB
testcase_12 AC 30 ms
5,376 KB
testcase_13 AC 30 ms
5,376 KB
testcase_14 AC 29 ms
5,376 KB
testcase_15 AC 30 ms
5,376 KB
testcase_16 AC 30 ms
5,376 KB
testcase_17 AC 30 ms
5,376 KB
testcase_18 AC 29 ms
5,376 KB
testcase_19 AC 29 ms
5,376 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