結果

問題 No.245 貫け！
コンテスト
ユーザー nola_suz
提出日時 2015-07-22 14:07:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 8 ms / 5,000 ms
コード長 3,058 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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 #
raw source code 

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