結果
問題 | No.2180 Comprehensive Line Segments |
ユーザー | MasKoaTS |
提出日時 | 2022-12-18 14:06:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,573 bytes |
コンパイル時間 | 2,177 ms |
コンパイル使用メモリ | 218,040 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-05-08 11:28:31 |
合計ジャッジ時間 | 4,182 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 113 ms
7,808 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 1 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 85 ms
7,936 KB |
testcase_10 | AC | 96 ms
7,808 KB |
testcase_11 | AC | 123 ms
7,936 KB |
testcase_12 | AC | 41 ms
6,944 KB |
testcase_13 | AC | 119 ms
7,936 KB |
testcase_14 | AC | 109 ms
7,936 KB |
testcase_15 | AC | 133 ms
8,064 KB |
testcase_16 | AC | 8 ms
6,944 KB |
testcase_17 | AC | 18 ms
6,944 KB |
testcase_18 | AC | 123 ms
7,936 KB |
testcase_19 | AC | 44 ms
6,940 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 16 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 4 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | AC | 8 ms
6,940 KB |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 19 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T> using V = vector<T>; const double EPS = 1e-10; struct EpsilonDouble { double x; EpsilonDouble(void) { x = 0.0; } EpsilonDouble(double x) { this->x = x; } static EpsilonDouble zero() { return EpsilonDouble(); } EpsilonDouble operator+(void) const { return EpsilonDouble(this->x); } EpsilonDouble operator-(void) const { return EpsilonDouble(-this->x); } EpsilonDouble operator+(const EpsilonDouble other) const { return EpsilonDouble(this->x + other.x); } EpsilonDouble operator-(const EpsilonDouble other) const { return EpsilonDouble(this->x - other.x); } EpsilonDouble operator*(const EpsilonDouble other) const { return EpsilonDouble(this->x * other.x); } EpsilonDouble operator/(const EpsilonDouble other) const { return EpsilonDouble(this->x / other.x); } bool operator==(const EpsilonDouble other) const { return (abs(this->x - other.x) < EPS); } bool operator!=(const EpsilonDouble other) const { return (((*this) == other) == false); } bool operator<(const EpsilonDouble other) const { return ((*this) != other and this->x < other.x); } bool operator>(const EpsilonDouble other) const { return ((*this) != other and this->x > other.x); } }; EpsilonDouble abs(EpsilonDouble x) { if (x < EpsilonDouble::zero()) { return -x; } return x; } int sgn(EpsilonDouble x) { if (x < EpsilonDouble::zero()) { return -1; } else if (x > EpsilonDouble::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 * 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); } 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<EpsilonDouble> > P(N); for (auto& p : P) { double x, y; cin >> x >> y; p.x = EpsilonDouble(x); p.y = EpsilonDouble(y); } if (N == 1) { cout << 1 << endl; return 0; } V<V<Vector2<EpsilonDouble> > > vec_lis(N, V<Vector2<EpsilonDouble> >(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<EpsilonDouble>::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<EpsilonDouble>& 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<EpsilonDouble>& 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; }