結果

問題 No.245 貫け！
ユーザー tottoripapertottoripaper
提出日時 2015-11-20 20:55:45
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 58 ms / 5,000 ms
コード長 1,833 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 67,968 KB
実行使用メモリ 4,356 KB
最終ジャッジ日時 2023-10-11 18:09:13
合計ジャッジ時間 2,247 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 2 ms
4,356 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,352 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 1 ms
4,352 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 2 ms
4,352 KB
testcase_09 AC 5 ms
4,352 KB
testcase_10 AC 6 ms
4,352 KB
testcase_11 AC 21 ms
4,352 KB
testcase_12 AC 57 ms
4,348 KB
testcase_13 AC 58 ms
4,348 KB
testcase_14 AC 57 ms
4,348 KB
testcase_15 AC 56 ms
4,352 KB
testcase_16 AC 57 ms
4,352 KB
testcase_17 AC 58 ms
4,352 KB
testcase_18 AC 57 ms
4,352 KB
testcase_19 AC 58 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <complex>
#include <algorithm>

typedef std::complex<double> P;

double dot(const P& p, const P& q){return std::real(std::conj(p) * q);}
double cross(const P& p, const P& q){return std::imag(std::conj(p) * q);}

bool areIntersectedLines(const P& p1, const P& p2, const P& q1, const P& q2){
    if(cross(p1-p2, q1-p2) == 0 && dot(p1-p2, q1-p2) > 0 &&
       0 <= norm(q1-p2) && norm(q1-p2) <= norm(p1-p2)){
        return true;
    }
    if(cross(p1-p2, q2-p2) == 0 && dot(p1-p2, q2-p2) > 0 &&
       0 <= norm(q2-p2) && norm(q2-p2) <= norm(p1-p2)){
        return true;
    }
    if(cross(q1-q2, p1-q2) == 0 && dot(q1-q2, p1-q2) > 0 &&
       0 <= norm(p1-q2) && norm(p1-q2) <= norm(q1-q2)){
        return true;
    }
    if(cross(q1-q2, p2-q2) == 0 && dot(q1-q2, p2-q2) > 0 &&
       0 <= norm(p2-q2) && norm(p2-q2) <= norm(q1-q2)){
        return true;
    }

    return (cross(p1-p2, q1-p2) * cross(p1-p2, q2-p2) <= 0) &&
        (cross(q1-q2, p1-q2) * cross(q1-q2, p2-q2) <= 0);
}

int N;
P ps[200];

int count(const P& p, const P& q){
    int res = 0;
    for(int i=0;i<N;i++){
        if(areIntersectedLines(p, q, ps[2*i], ps[2*i+1])){
            res += 1;
        }
    }
    return res;
}

int main(){
    scanf("%d", &N);
    
    for(int i=0;i<N;i++){
        double x, y, z, w;
        scanf("%lf %lf %lf %lf", &x, &y, &z, &w);

        ps[2*i] = P{x, y};
        ps[2*i+1] = P{z, w};
    }

    int res = 0;
    for(int i=0;i<2*N;i++){
        for(int j=i+1;j<2*N;j++){
            P p = ps[i], q = ps[j];
            
            p -= 100.0 * (q - p);
            q -= 100.0 * (p - q);

            // printf("%d, %d: (%lf, %lf), (%lf, %lf)\n", i, j, real(p), imag(p), real(q), imag(q));
            
            res = std::max(res, count(p, q));
        }
    }

    printf("%d\n", res);
}
0