結果

問題 No.2180 Comprehensive Line Segments
ユーザー MasKoaTSMasKoaTS
提出日時 2022-10-13 14:48:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,446 bytes
コンパイル時間 2,738 ms
コンパイル使用メモリ 222,132 KB
実行使用メモリ 10,268 KB
最終ジャッジ日時 2024-04-28 10:35:14
合計ジャッジ時間 9,094 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, l, n) for (int i = (l); i < (n); i++)
#define all(x) x.begin(), x.end()
#define last(v) v[v.size() - 1]
#define inf 1000000000
using namespace std;
using ll = long long;
template <class T>	using V = vector<T>;

inline ll gcd(ll x, ll y) {
	x = abs(x);	y = abs(y);
	while (y != 0) {
		ll r = x % y;
		x = y;
		y = r;
	}
	return x;
}

inline ll lcm(ll x, ll y) {
	ll g = gcd(x, y);
	return x / g * y;
}

struct Fraction {
	ll num;
	ll den;

	Fraction(void) {
		num = 0ll;
		den = 1ll;
	}

	Fraction(ll num, ll den) {
		assert(den != 0);
		ll g = gcd(num, den);
		num /= g;
		den /= g;
		if (den < 0) {
			num = -num;
			den = -den;
		}
		this->num = num;
		this->den = den;
	}

	Fraction operator+(const Fraction other) const {
		ll l = lcm(this->den, other.den);
		ll a = l / this->den;
		ll b = l / other.den;
		ll nnum = this->num * a + other.num * b;
		ll nden = l;
		return Fraction(nnum, nden);
	}

	Fraction operator-(const Fraction other) const {
		Fraction f = Fraction(-other.num, other.den);
		return (*this) + f;
	}

	Fraction operator*(const Fraction other) const {
		ll nnum = this->num * other.num;
		ll nden = this->den * other.den;
		return Fraction(nnum, nden);
	}

	Fraction operator/(const Fraction other) const {
		Fraction f = Fraction(other.den, other.num);
		return (*this) * f;
	}

	bool operator<(const Fraction other) const {
		ll l = lcm(this->den, other.den);
		ll a = l / this->den;
		ll b = l / other.den;
		return (this->num * a < other.num* b);
	}

	bool operator==(const Fraction other) const {
		ll l = lcm(this->den, other.den);
		ll a = l / this->den;
		ll b = l / other.den;
		return (this->num * a == other.num * b);
	}

	bool operator!=(const Fraction other) const {
		return (((*this) == other) == false);
	}
};
const Fraction zero = Fraction();

inline Fraction abs_frac(Fraction x) {
	return ((x < zero) ? zero - x : x);
}

inline int sgn(Fraction x) {
	if (zero < x) {
		return 1;
	}
	if (x < zero) {
		return -1;
	}
	return 0;
}


struct Vector2 {
	Fraction x;
	Fraction y;

	Vector2(void) {
		x = zero;
		y = zero;
	}

	Vector2(Fraction x, Fraction y) {
		this->x = x;
		this->y = y;
	}

	Vector2 operator+(const Vector2 other) const {
		return Vector2(other.x + this->x, other.y - this->y);
	}

	Vector2 operator-(const Vector2 other) const {
		return Vector2(other.x - this->x, other.y - this->y);
	}

	Fraction operator*(const Vector2 other) const {
		return this->x * other.y - this->y * other.x;
	}

	bool operator<(const Vector2 other) const {
		return tie(this->x, this->y) < tie(other.x, other.y);
	}

	bool operator==(const Vector2 other) const {
		return tie(this->x, this->y) == tie(other.x, other.y);
	}

	bool operator!=(const Vector2 other) const {
		return tie(this->x, this->y) != tie(other.x, other.y);
	}
};
const Vector2 zero_vector = Vector2();

inline Vector2 normalize_vector(Vector2 v) {
	assert(v.x != zero or v.y != zero);
	Fraction norm = v.x * v.x + v.y * v.y;
	return Vector2(v.x * abs_frac(v.x) / norm, v.y * abs_frac(v.y) / norm);
}


/*
* Main Code
*/

int main(void) {
	int N;	cin >> N;
	V<Vector2> P(N);
	rep(i, 0, N) {
		ll x, y;	cin >> x >> y;
		P[i] = { Fraction(x,1ll),Fraction(y,1ll) };
	}

	if (N == 1) {
		cout << 1 << endl;
		return 0;
	}

	V<V<Vector2> > vectors(N, V<Vector2>(N));
	rep(i, 0, N - 1) {
		rep(j, i + 1, N) {
			vectors[i][j] = normalize_vector(P[j] - P[i]);
			vectors[j][i] = normalize_vector(P[i] - P[j]);
		}
	}

	int ans = N;
	V<int> num(N);
	rep(i, 0, N) {
		num[i] = i;
	}
	do {
		bool flag = false;
		V<Vector2> p(N);
		rep(i, 0, N) {
			p[i] = P[num[i]];
		}
		V<Vector2> vec = { vectors[num[0]][num[1]] };
		rep(i, 1, N - 1) {
			Vector2 v = vectors[num[i]][num[i + 1]];
			if (last(vec) == v) {
				continue;
			}
			if (last(vec) * v == zero) {
				flag = true;
				break;
			}
			vec.push_back(v);
		}
		if (flag) {
			continue;
		}

		int M = vec.size();
		if (M <= 2) {
			ans = min(ans, M);
			continue;
		}

		V<pair<int, int> > dp(M - 1, { -1,-1 });
		dp[0].first = 0;
		rep(i, 1, M - 1) {
			Vector2 v1 = vec[i - 1], v2 = vec[i], v3 = vec[i + 1];
			int s1 = sgn(v1 * v2), s2 = sgn(v2 * v3), s3 = sgn(v1 * v3);
			if (s1 == s2 and s2 == s3) {
				dp[i].second = dp[i - 1].first + 1;
			}
			dp[i].first = max(dp[i - 1].first, dp[i - 1].second);
		}
		ans = min(ans, M - max(dp[M - 2].first, dp[M - 2].second));
	} while (next_permutation(all(num)));

	cout << ans << endl;

	return 0;
}
0