結果
問題 | No.245 貫け! |
ユーザー | tkzw_21 |
提出日時 | 2015-07-17 23:27:20 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,316 bytes |
コンパイル時間 | 1,567 ms |
コンパイル使用メモリ | 171,504 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-08 09:34:01 |
合計ジャッジ時間 | 8,178 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
5,248 KB |
testcase_01 | AC | 54 ms
5,376 KB |
testcase_02 | AC | 53 ms
5,376 KB |
testcase_03 | AC | 44 ms
5,376 KB |
testcase_04 | AC | 56 ms
5,376 KB |
testcase_05 | AC | 64 ms
5,376 KB |
testcase_06 | AC | 72 ms
5,376 KB |
testcase_07 | AC | 41 ms
5,376 KB |
testcase_08 | AC | 145 ms
5,376 KB |
testcase_09 | WA | - |
testcase_10 | AC | 275 ms
5,376 KB |
testcase_11 | AC | 423 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 589 ms
5,376 KB |
testcase_16 | AC | 557 ms
5,376 KB |
testcase_17 | AC | 572 ms
5,376 KB |
testcase_18 | AC | 561 ms
5,376 KB |
testcase_19 | AC | 553 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;const double EPS = 1e-8;const double INF = 1e12;typedef complex<double> P;namespace std {bool operator < (const P& a, const P& b) {return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);}}double cross(const P& a, const P& b) {return imag(conj(a)*b);}double dot(const P& a, const P& b) {return real(conj(a)*b);}struct L : public vector<P> {L(const P &a, const P &b) {push_back(a); push_back(b);}};int ccw(P a, P b, P c) {b -= a; c -= a;if (cross(b, c) > 0) return +1; // counter clockwiseif (cross(b, c) < 0) return -1; // clockwiseif (dot(b, c) < 0) return +2; // c--a--b on lineif (norm(b) < norm(c)) return -2; // a--b--c on linereturn 0;}typedef vector<P> G;struct C {P p; double r;C(const P &p, double r) : p(p), r(r) { }};bool intersectLL(const L &l, const L &m) {return abs(cross(l[1]-l[0], m[1]-m[0])) > EPS || // non-parallelabs(cross(l[1]-l[0], m[0]-l[0])) < EPS; // same line}bool intersectLS(const L &l, const L &s) {return cross(l[1]-l[0], s[0]-l[0])* // s[0] is left of lcross(l[1]-l[0], s[1]-l[0]) < EPS; // s[1] is right of l}bool intersectSS(const L &s, const L &t) {return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;}int main(void){int n;cin >> n;vector<L> lines;int a,b,c,d;for(int i=0;i<n;i++){cin >> a >> b >> c >> d;P p1(a,b),p2(c,d);L l(p1,p2);lines.push_back(l);}vector<pair<int,int>> lp;for(int i=-100;i<=100;i++){lp.push_back(make_pair(i,-100));lp.push_back(make_pair(i,100));lp.push_back(make_pair(-100,i));lp.push_back(make_pair(100,i));}int ret =0;for(int i=0;i<lp.size();i++){for(int j=0;j<lp.size();j++){if(i == j)continue;int cnt =0;P p1(lp[i].first,lp[i].second),p2(lp[j].first,lp[j].second);L l(p1,p2);for(int k=0;k<n;k++){if(intersectSS(l,lines[k])){cnt++;}}ret = max(ret,cnt);}}cout << ret << endl;return 0;}