結果
問題 | No.245 貫け! |
ユーザー | tottoripaper |
提出日時 | 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 |
ソースコード
#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); }