結果

問題 No.245 貫け！
ユーザー nola_suz
提出日時 2015-07-22 14:07:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 3,058 bytes
コンパイル時間 1,557 ms
コンパイル使用メモリ 170,604 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 11:47:21
合計ジャッジ時間 1,948 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define reep(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) reep((i),0,(n))
typedef pair<int,int> pii;
typedef pair<pii,pii> pp;
#define F first
#define S second
#define PB push_back
/***********************************************************************************/
typedef complex<double> P;
 
// 許容する誤差ε
#define EPS (1e-10)
// 2つのスカラーが等しいかどうか
#define EQ(a,b) (abs((a)-(b)) < EPS)
// 2つのベクトルが等しいかどうか
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
 
// 内積 (dot product) : a・b = |a||b|cosΘ
double dot(P a, P b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}
 
// 外積 (cross product) : a×b = |a||b|sinΘ
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}
 
// 2直線の直交判定 : a⊥b <=> dot(a, b) = 0
int is_orthogonal(P a1, P a2, P b1, P b2) {
  return EQ( dot(a1-a2, b1-b2), 0.0 );
}
 
// 2直線の平行判定 : a//b <=> cross(a, b) = 0
int is_parallel(P a1, P a2, P b1, P b2) {
  return EQ( cross(a1-a2, b1-b2), 0.0 );
}
 
// 点cが直線a,b上にあるかないか
int is_point_on_line(P a, P b, P c) {
  return EQ( cross(b-a, c-a), 0.0 );
}
 
// 点a,bを通る直線と点cとの距離
double distance_l_p(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}
 
// 点a,bを端点とする線分と点cとの距離
double distance_ls_p(P a, P b, P c) {
  if ( dot(b-a, c-a) < EPS ) return abs(c-a);
  if ( dot(a-b, c-b) < EPS ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}
 
// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_ls(P a1, P a2, P b1, P b2) {
    // if(is_point_on_line(a1,a2,b1)) return true;
    // if(is_point_on_line(a1,a2,b2)) return true;
    // if(is_point_on_line(b1,b2,a1)) return true;
    // if(is_point_on_line(b1,b2,a2)) return true;
    // if(is_parallel(a1,a2,b1,b2)) return false;
    // return false;
  return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS );
}
/*******************************************************************/
bool foo(pii a,pii b,pii c,pii d){
    pair<P,P> x(P(a.F,a.S),P(b.F,b.S));
    pair<P,P> y(P(c.F,c.S),P(d.F,d.S));
    return is_intersected_ls(x.F,x.S,y.F,y.S);
}
int check(pii a,pii b,vector<pp> &v){
    int ret=0;
    rep(i,v.size()){
        if(foo(a,b,v[i].F,v[i].S)){
            ret++;
            // if(a==pii(0,1)&&b==pii(0,0)){
                // cout<<"match "<<v[i].F.F<<" "<<v[i].F.S<<" "<<v[i].S.F<<" "<<v[i].S.S<<endl;
            // }
        }
    }
    return ret;
}
int main(){
    int n;
    cin>>n;
    vector<pp> v(n);
    vector<pii> w;
    rep(i,n){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        v[i]=make_pair(pii(a,b),pii(c,d));
        w.PB(pii(a,b));
        w.PB(pii(c,d));
    }
    sort(w.begin(),w.end());
    w.erase(unique(w.begin(),w.end()),w.end());
    int ans=0;
    rep(i,w.size()){
        rep(j,i){
            int t=check(w[i],w[j],v);
            // if(t==4){
                // cout<<i<<" "<<j<<endl;
                // cout<<w[i].F<<" "<<w[i].S<<" "<<w[j].F<<" "<<w[j].S<<endl;
                // return 0;
            // }
            ans=max(ans,t);
        }
    }
    cout<<ans<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0