結果

問題 No.245 貫け！
ユーザー cande398cande398
提出日時 2018-06-11 20:28:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,350 bytes
コンパイル時間 789 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-30 13:44:00
合計ジャッジ時間 1,574 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,948 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <complex>
#include <iostream>
#include <algorithm>
#include <vector>
#define EPS (1e-10)
using namespace std;

typedef complex<double> P;

// 内積 (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());
}

// a1,a2を端点とする線分とb1,b2を端点とする線分の交差判定
int is_intersected_ls(P a1, P a2, P b1, P b2) {
  return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
         ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

int main(void)
{
	int N;
	cin >> N;
	vector<P> start(N);
	vector<P> end(N);
	double ax, ay, bx, by;
	for(int i = 0; i < N; i++) {
		cin >> ax >> ay >> bx >> by;
		start[i] = P(ax, ay);
		end[i] = P(bx, by);
	}
	
	int max = 0;
	for(int i = -100; i < 100; i++) {
		int count = 0;
		for(int j = 0; j < N; j++) {
			if(is_intersected_ls(P(i, 100), P(i, -100), start[j], end[j]) == 1) {
				count++;
			}
		}
		if(max < count) {
			max = count;
		}
	}
	for(int i = -100; i < 100; i++) {
		int count = 0;
		for(int j = 0; j < N; j++) {
			if(is_intersected_ls(P(100, i), P(-100, i), start[j], end[j]) == 1) {
				count++;
			}
		}
		if(max < count) {
			max = count;
		}
	}
	cout << max << endl;
}
0