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

• 問題: No.245 貫け！
• ユーザー: ciel
• 提出日時: 2015-07-18 00:39:45
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 10 ms / 5,000 ms
• コード長: 1,002 bytes
• コンパイル時間: 632 ms
• コンパイル使用メモリ: 75,520 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-22 18:41:49
• 合計ジャッジ時間: 1,583 ms
• ジャッジサーバーID （参考情報）: judge15 / judge12

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

ソースコード

#include <vector>
#include <complex>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cfloat>
using namespace std;
typedef long long val_t;
typedef complex<val_t> P;
typedef vector<P> VP;

val_t cross(const P &a,const P &b){return (conj(a)*b).imag();}
val_t dot(const P &a,const P &b){return (conj(a)*b).real();}
bool intersectLS(const VP &l, const VP &s) {
	return cross(l[1]-l[0], s[0]-l[0])*       // s[0] is left of l
		cross(l[1]-l[0], s[1]-l[0]) <= 0; // s[1] is right of l
}
int main(){
	int n;
	scanf("%d",&n);
	vector<VP> lst(n);
	for(int i=0;i<n;i++){
		long long sx,sy,ex,ey;
		scanf("%lld%lld%lld%lld",&sx,&sy,&ex,&ey);
		lst[i]={P(sx,sy),P(ex,ey)};
	}
	int R=1;
	for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
		vector<VP> x={{lst[i][0],lst[j][0]},{lst[i][1],lst[j][0]},{lst[i][0],lst[j][1]},{lst[i][1],lst[j][1]}};
		for(auto &e:x){
			if(e[0]==e[1])continue; //bah!!!
			int r=0;
			for(int k=0;k<n;k++)r+=intersectLS(e,lst[k]);
			if(R<r)R=r;
		}
	}
	printf("%d\n",R);
}