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

• 問題: No.245 貫け！
• ユーザー: nola_suz
• 提出日時: 2015-07-22 13:35:09
• 言語: C++11 (gcc 11.4.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	WA	-
testcase_03	AC	2 ms; 5,376 KB
testcase_04	WA	-
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	36 ms; 5,376 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-

ソースコード

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