結果
問題 | No.245 貫け! |
ユーザー |
![]() |
提出日時 | 2018-06-11 20:29:39 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 19 ms / 5,000 ms |
コード長 | 2,309 bytes |
コンパイル時間 | 1,338 ms |
コンパイル使用メモリ | 164,408 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 13:45:01 |
合計ジャッジ時間 | 2,205 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<n;i++)#define X real()#define Y imag()using namespace std;using P = complex<double>;using L = pair<P,P>;const double EPS=1e-9;// 内積 dot(a,b) = |a||b|cosθdouble dot(P a, P b) {return (conj(a)*b).X;}// 外積 cross(a,b) = |a||b|sinθdouble cross(P a, P b) {return (conj(a)*b).Y;}// 直線と線分bool isecLS(P a1, P a2, P b1, P b2) {return cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS;}int main(void){int max=1;int n;int a,b,c,d;cin>>n;vector<L> l(n);rep(i,n){cin>>a>>b>>c>>d;l[i]=L(P(a,b),P(c,d));}rep(i,n){rep(j,n){if(i==j)continue;int tmp=0;if(l[i].first!=l[j].first){rep(k,n){if(isecLS(l[i].first,l[j].first,l[k].first,l[k].second)){tmp++;}}if(max<tmp){max=tmp;//cout<<i<<" "<<j<<" "<<max<<" "<<1<<endl;}}tmp=0;if(l[i].first!=l[j].second){rep(k,n){if(isecLS(l[i].first,l[j].second,l[k].first,l[k].second)){tmp++;}}if(max<tmp){max=tmp;//cout<<i<<" "<<j<<" "<<max<<" "<<2<<endl;}}tmp=0;if(l[i].second!=l[j].second){rep(k,n){if(isecLS(l[i].second,l[j].second,l[k].first,l[k].second)){tmp++;}}if(max<tmp){max=tmp;//cout<<i<<" "<<j<<" "<<max<<" "<<3<<endl;}}tmp=0;if(l[i].second!=l[j].first){rep(k,n){if(isecLS(l[i].second,l[j].first,l[k].first,l[k].second)){tmp++;}}if(max<tmp){max=tmp;//cout<<i<<" "<<j<<" "<<max<<" "<<4<<endl;}}}}cout<<max<<endl;}