結果

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

ソースコード

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

// 2-D kika
#define EPS 1e-8
 
typedef complex<double> P;
typedef const P &rP;
typedef pair<P,P> seg;
//naiseki
double dot(rP a, rP b){
    return real(a) * real(b) + imag(a) * imag(b);
}
//gaiseki
double cross(rP a, rP b){
    return real(a) * imag(b) - imag(a) * real(b);
}
double norm(P x){
	return real(x) * real(x) + imag(x) * imag(x);
}
 
int ccw(const seg &s, P c){
    P b = s.second - s.first;
    c -= s.first;
    double cr = cross(b, c);
    if(cr < -EPS){ return 1; }
    if(cr > EPS){ return -1; }
    if(dot(b, c) < -EPS){ return 2; }
    if(norm(b) < norm(c) - EPS){ return -2; }
    return 0;
}
 
bool intersectSS(const seg &s, const seg &t){
    return ccw(s, t.first) * ccw(s, t.second) <= 0 &&
           ccw(t, s.first) * ccw(t, s.second) <= 0;
}


bool foo(pii a,pii b,pii c,pii d){
	seg x(P(a.F,a.S),P(b.F,b.S));
	seg y(P(c.F,c.S),P(d.F,d.S));
	return intersectSS(x,y);
}
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++;
	}
	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(b,c));
		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){
			ans=max(ans,check(w[i],w[j],v));
		}
	}
	cout<<ans<<endl;
}
0