結果

問題 No.245 貫け！
コンテスト
ユーザー tottoripaper
提出日時 2015-11-20 20:55:45
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 33 ms / 5,000 ms
コード長 1,833 bytes
記録
コンパイル時間 507 ms
コンパイル使用メモリ 69,152 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 17:05:37
合計ジャッジ時間 1,733 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:46:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   46 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:50:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |         scanf("%lf %lf %lf %lf", &x, &y, &z, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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