結果
| 問題 | No.2180 Comprehensive Line Segments |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-26 16:02:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 340 ms / 5,000 ms |
| コード長 | 4,514 bytes |
| コンパイル時間 | 2,401 ms |
| コンパイル使用メモリ | 208,604 KB |
| 実行使用メモリ | 7,936 KB |
| 最終ジャッジ日時 | 2025-03-26 16:03:00 |
| 合計ジャッジ時間 | 6,352 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 25 |
ソースコード
#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;}