#38301 (C++11) No.245 貫け！

• 問題: No.245 貫け！
• ユーザー: nola_suz
• 提出日時: 2015-07-22 14:07:17
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 17 ms / 5,000 ms
• コード長: 3,058 bytes
• コンパイル時間: 1,407 ms
• コンパイル使用メモリ: 157,244 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-22 21:12:33
• 合計ジャッジ時間: 2,386 ms
• ジャッジサーバーID （参考情報）: judge11 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,380 KB
testcase_01	AC	1 ms; 4,376 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	1 ms; 4,380 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	1 ms; 4,376 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	2 ms; 4,376 KB
testcase_09	AC	2 ms; 4,380 KB
testcase_10	AC	3 ms; 4,376 KB
testcase_11	AC	7 ms; 4,376 KB
testcase_12	AC	16 ms; 4,376 KB
testcase_13	AC	16 ms; 4,376 KB
testcase_14	AC	16 ms; 4,380 KB
testcase_15	AC	17 ms; 4,376 KB
testcase_16	AC	16 ms; 4,376 KB
testcase_17	AC	16 ms; 4,376 KB
testcase_18	AC	16 ms; 4,380 KB
testcase_19	AC	16 ms; 4,376 KB

ソースコード

#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;
}