#903639 (C++17) No.2180 Comprehensive Line Segments

• 問題: No.2180 Comprehensive Line Segments
• ユーザー: MasKoaTS
• 提出日時: 2023-08-13 12:39:56
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 299 ms / 5,000 ms
• コード長: 4,514 bytes
• コンパイル時間: 2,840 ms
• コンパイル使用メモリ: 215,352 KB
• 実行使用メモリ: 7,936 KB
• 最終ジャッジ日時: 2024-05-01 05:57:10
• 合計ジャッジ時間: 6,130 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	293 ms; 7,808 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,944 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	2 ms; 6,940 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	176 ms; 7,808 KB
testcase_10	AC	191 ms; 7,936 KB
testcase_11	AC	298 ms; 7,808 KB
testcase_12	AC	79 ms; 6,940 KB
testcase_13	AC	291 ms; 7,680 KB
testcase_14	AC	251 ms; 7,808 KB
testcase_15	AC	299 ms; 7,808 KB
testcase_16	AC	11 ms; 6,940 KB
testcase_17	AC	31 ms; 6,944 KB
testcase_18	AC	273 ms; 7,808 KB
testcase_19	AC	97 ms; 6,940 KB
testcase_20	AC	1 ms; 6,944 KB
testcase_21	AC	29 ms; 6,944 KB
testcase_22	AC	2 ms; 6,940 KB
testcase_23	AC	4 ms; 6,944 KB
testcase_24	AC	2 ms; 6,944 KB
testcase_25	AC	11 ms; 6,944 KB
testcase_26	AC	268 ms; 7,808 KB
testcase_27	AC	31 ms; 6,940 KB
testcase_28	AC	31 ms; 6,944 KB

ソースコード

#include <bits/stdc++.h>
#define sgn(x) ((x) < 0 ? -1 : ((x) == 0 ? 0 : 1))
using namespace std;
template <class T>	using V = vector<T>;


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 * abs(v.x) / norm, v.y * 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);
	}

    Vector2 operator-(void) const {
		return Vector2(-(this->x), -(this->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<int> > P(N);
	for (auto& p : P) {
		cin >> p.x >> p.y;
	}

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

	V<V<Vector2<int> > > vectors(N, V<Vector2<int> >(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;
			}
			vectors[i][j] = 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<int>& v1 = vectors[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<int>& v2 = vectors[v_now][v_next1], v3 = vectors[v_next1][v_next2];
                        int d = 1, e = 1;
						if (v_now == v_next1) {
							c_next = c_now + 1 - Vector2<int>::same_inclination(v1, v3);
						}
						else {
							d = e = Vector2<int>::same_inclination(v1, v2) + Vector2<int>::same_inclination(v2, v3);
							if (e == 0) {
								int s1 = sgn(v1 * v2), s2 = sgn(v2 * v3), s3 = sgn(v1 * v3);
								e = (s1 == s2 and s2 == s3);
							}
							c_next = c_now + 2 - e;
						}
						if (dp[b_next][v_next1][v_next2] > c_next) {
                            dp[b_next][v_next1][v_next2] = c_next;
						}
						
                        // 1点だけ通る場合を考慮
                        if(v_now == v_next1 or d != 0){
                            continue;
                        }
                        int c_in = c_next + e;
                        for(int v_in = 0; v_in < N; ++v_in){
                            if((b_next >> v_in) & 1){
                                continue;
                            }
                            Vector2<int>& v4 = vectors[v_now][v_in];
                            Vector2<int>& v5 = vectors[v_next1][v_in];
                            int s1 = sgn(v1 * v4), s2 = sgn(v4 * v2), s3 = sgn(v1 * v2);
                            if(s1 != s2 || s2 != s3){
                                continue;
                            }
                            s1 = sgn((-v2) * v5), s2 = sgn(v5 * (-v3)), s3 = sgn((-v2) * (-v3));
                            if(s1 != s2 || s2 != s3){
                                continue;
                            }
                            int b_in = b_next | (1 << v_in);
                            if(dp[b_in][v_next1][v_next2] <= c_in){
                                continue;
                            }
                            dp[b_in][v_next1][v_next2] = c_in;
					    }
                    }
				}
			}
		}
	}

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

	return 0;
}