結果

問題 No.2180 Comprehensive Line Segments
コンテスト
ユーザー MasKoaTS
提出日時 2022-12-18 13:52:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,298 bytes
コンパイル時間 2,592 ms
コンパイル使用メモリ 217,624 KB
最終ジャッジ日時 2025-02-09 16:07:32
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 21 WA * 2 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>	using V = vector<T>;


struct Fraction {
	ll numor;
	ll denom;

	static ll gcd(ll x, ll y) {
		if (x < 0) {
			x = -x;
		}
		if (y < 0) {
			y = -y;
		}
		while (y != 0) {
			ll r = x % y;
			x = y;
			y = r;
		}
		return x;
	}

	static ll lcm(ll x, ll y) {
		return x / gcd(x, y) * y;
	}

	Fraction(void) {
		numor = 0ll;
		denom = 1ll;
	}

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

	static Fraction abs(Fraction x) {
		if (x.numor < 0) {
			return -x;
		}
		return x;
	}

	static Fraction zero(void) {
		return Fraction();
	}

	Fraction operator+(void) const {
		return *this;
	}

	Fraction operator-(void) const {
		return Fraction() - (*this);
	}

	Fraction operator+(const Fraction other) const {
		ll l = lcm(this->denom, other.denom);
		ll a = l / this->denom;
		ll b = l / other.denom;
		ll new_numor = this->numor * a + other.numor * b;
		ll new_denom = l;
		return Fraction(new_numor, new_denom);
	}

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

	Fraction operator*(const Fraction other) const {
		ll new_numor = this->numor * other.numor;
		ll new_denom = this->denom * other.denom;
		return Fraction(new_numor, new_denom);
	}

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

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

	bool operator>(const Fraction other) const {
		return (other < (*this));
	}

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

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

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


template <class T>
struct Vector2 {
	T x;
	T y;

	Vector2(void) {

	}

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

	static Vector2 normalize(Vector2 v) {
		T norm = v.x * v.x + v.y * v.y;
		return Vector2(v.x * Fraction::abs(v.x) / norm, v.y * Fraction::abs(v.y) / norm);
	}

	static bool same_inclination(Vector2& v1, Vector2& v2) {
		return (v1 * v2 == 0 and (v1.x * v2.x > 0 or v1.y * v2.y > 0));
	}

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

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

	T 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);
	}
};


int main(void) {
	int N;	cin >> N;
	V<Vector2<Fraction> > P(N);
	for (auto& p : P) {
		ll x, y;	cin >> x >> y;
		p.x = Fraction(x, 1);
		p.y = Fraction(y, 1);
	}

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

	V<V<Vector2<Fraction> > > vec_lis(N, V<Vector2<Fraction> >(N));
	V<V<V<int> > > dp(1 << N, V<V<int> >(N, V<int>(N, N)));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i == j) {
				continue;
			}
			vec_lis[i][j] = Vector2<Fraction>::normalize(P[j] - P[i]);
			dp[(1 << i) | (1 << j)][i][j] = 1;
		}
	}

	int goal = (1 << N) - 1;
	for (int b_now = 3; b_now < goal; ++b_now) {
		for (int v_prev = 0; v_prev < N; ++v_prev) {
			for (int v_now = 0; v_now < N; ++v_now) {
				if (v_prev == v_now or dp[b_now][v_prev][v_now] == N or ((b_now >> v_prev) & 1) == 0 or ((b_now >> v_now) & 1) == 0) {
					continue;
				}
				int c_now = dp[b_now][v_prev][v_now], c_next = 0;
				Vector2<Fraction>& v1 = vec_lis[v_prev][v_now];
				for (int v_next1 = 0; v_next1 < N; ++v_next1) {
					for (int v_next2 = 0; v_next2 < N; ++v_next2) {
						if (v_next1 == v_next2 or (((b_now >> v_next1) & 1) and v_now != v_next1) or ((b_now >> v_next2) & 1)) {
							continue;
						}
						int b_next = b_now | (1 << v_next1) | (1 << v_next2);
						Vector2<Fraction>& v2 = vec_lis[v_now][v_next1], v3 = vec_lis[v_next1][v_next2];
						if (v_now == v_next1) {
							c_next = c_now + 1 - (v1 == v3);
						}
						else {
							int d = (v1 == v2) + (v2 == v3);
							if (d == 0) {
								int s1 = sgn(v1 * v2), s2 = sgn(v2 * v3), s3 = sgn(v1 * v3);
								d = (s1 == s2 and s2 == s3);
							}
							c_next = c_now + 2 - d;
						}
						if (dp[b_next][v_next1][v_next2] <= c_next) {
							continue;
						}
						dp[b_next][v_next1][v_next2] = c_next;
					}
				}
			}
		}
	}

	int ans = N;
	for (auto v : dp[goal]) {
		for (auto k : v) {
			if (ans <= k) {
				continue;
			}
			ans = k;
		}
	}
	cout << ans << endl;

	return 0;
}
0