結果
| 問題 | No.2180 Comprehensive Line Segments |
| ユーザー |
👑  rin204
|
| 提出日時 | 2023-01-06 23:33:28 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,266 bytes |
| コンパイル時間 | 2,202 ms |
| コンパイル使用メモリ | 204,320 KB |
| 最終ジャッジ日時 | 2025-02-10 00:29:31 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 22 WA * 3 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;using ull = unsigned long long;template <class T>using pq = priority_queue<T>;template <class T>using qp = priority_queue<T, vector<T>, greater<T>>;#define vec(T, A, ...) vector<T> A(__VA_ARGS__);#define vvec(T, A, h, ...) vector<vector<T>> A(h, vector<T>(__VA_ARGS__));#define vvvec(T, A, h1, h2, ...) vector<vector<vector<T>>> A(h1, vector<vector<T>>(h2, vector<T>(__VA_ARGS__)));#define endl "\n"#define spa ' '#define len(A) A.size()#define all(A) begin(A), end(A)#define fori1(a) for(ll _ = 0; _ < (a); _++)#define fori2(i, a) for(ll i = 0; i < (a); i++)#define fori3(i, a, b) for(ll i = (a); i < (b); i++)#define fori4(i, a, b, c) for(ll i = (a); ((c) > 0 || i > (b)) && ((c) < 0 || i < (b)); i += (c))#define overload4(a, b, c, d, e, ...) e#define fori(...) overload4(__VA_ARGS__, fori4, fori3, fori2, fori1)(__VA_ARGS__)#define INT(...) int __VA_ARGS__; inp(__VA_ARGS__);#define LL(...) ll __VA_ARGS__; inp(__VA_ARGS__);#define STRING(...) string __VA_ARGS__; inp(__VA_ARGS__);#define CHAR(...) char __VA_ARGS__; inp(__VA_ARGS__);#define VEC(T, A, n) vector<T> A(n); inp(A);#define VVEC(T, A, n, m) vector<vector<T>> A(n, vector<T>(m)); inp(A);const ll MOD1 = 1000000007;const ll MOD9 = 998244353;template<class T> auto min(const T& a){return *min_element(all(a));}template<class T> auto max(const T& a){return *max_element(all(a));}template <class T, class S>inline bool chmax(T &a, const S &b) {return (a < b ? a = b, 1 : 0);}template <class T, class S>inline bool chmin(T &a, const S &b) {return (a > b ? a = b, 1 : 0);}void print(){cout << endl;}template <class Head, class... Tail>void print(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(Tail)) cout << spa;print(forward<Tail>(tail)...);}template<typename T>void print(vector<T> &A){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i == n - 1) cout << endl;else cout << spa;}}template<typename T>void print(vector<vector<T>> &A){for(auto &row: A) print(row);}template<typename T, typename S>void print(pair<T, S> &A){cout << A.first << spa << A.second << endl;}template<typename T, typename S>void prisep(vector<T> &A, S sep){int n = A.size();for(int i = 0; i < n; i++){cout << A[i];if(i == n - 1) cout << endl;else cout << sep;}}template<typename T, typename S>void priend(T A, S end){cout << A << end;}template<typename T>void priend(T A){priend(A, spa);}template<class... T>void inp(T&... a){(cin >> ... >> a);}template<typename T>void inp(vector<T> &A){for(auto &a:A) cin >> a;}template<typename T>void inp(vector<vector<T>> &A){for(auto &row:A) inp(row);}template<typename T, typename S>void inp(pair<T, S> &A){inp(A.first, A.second);}template<typename T, typename S>void inp(vector<pair<T, S>> &A){for(auto &row: A) inp(row.first, row.second);}template<typename T>T sum(vector<T> &A){T tot = 0;for(auto a:A) tot += a;return tot;}void solve(){INT(n);vector<pair<ll, ll>> point(n);inp(point);if(n <= 2){print(1);return;}const ll inf = 1LL << 60;auto f=[&](int bit, int i, int j, int k, int t){return (((bit * n + i) * n + j) * n + k) * 2 + t;};vec(ll, dp, (1 << n) * n * n * n * 2, inf);auto dot=[&](pair<ll, ll> d1, pair<ll, ll> d2){return d1.first * d2.first + d1.second * d2.second;};auto cross=[&](pair<ll, ll> d1, pair<ll, ll> d2){return d1.first * d2.second - d1.second * d2.first;};auto line3=[&](int i, int j, int k){if(i == j) return true;ll dx1 = point[j].first - point[i].first;ll dy1 = point[j].second - point[i].second;ll dx2 = point[k].first - point[j].first;ll dy2 = point[k].second - point[j].second;pair<ll, ll> d1 = {dx1, dy1};pair<ll, ll> d2 = {dx2, dy2};if(cross(d1, d2) != 0) return false;return dot(d1, d2) > 0;};fori(bit, 1, 1 << n){vec(int, ind, 0);int pc = 0;fori(i, n){if((bit >> i) & 1){pc++;ind.push_back(i);}}if(pc == 1){int i = ind[0];dp[f(bit, i, i, i, 0)] = 1;dp[f(bit, i, i, i, 1)] = 1;continue;}else if(pc == 2){int i = ind[0];int j = ind[1];dp[f(bit, i, i, j, 1)] = 1;continue;}for(auto i:ind) for(auto j:ind){for(auto k:ind){if(i == k || j == k) continue;for(auto l:ind){if(i == l || j == l || k == l) continue;if(line3(i, j, k)){if(line3(j, k, l)){chmin(dp[f(bit, j, k, l, 1)], dp[f((bit) ^ (1 << l), i, j, k, 1)]);chmin(dp[f(bit, j, k, l, 1)], dp[f((bit) ^ (1 << l), i, j, k, 0)]);}else{chmin(dp[f(bit, j, k, l, 1)], dp[f((bit) ^ (1 << l), i, j, k, 1)] + 1);chmin(dp[f(bit, j, k, l, 0)], dp[f((bit) ^ (1 << l), i, j, k, 1)] + 1);}}else if(line3(j, k, l)){chmin(dp[f(bit, j, k, l, 1)], dp[f((bit) ^ (1 << l), i, j, k, 1)]);chmin(dp[f(bit, j, k, l, 1)], dp[f((bit) ^ (1 << l), i, j, k, 0)]);}else{ll ji1 = point[j].first - point[i].first;ll ji2 = point[j].second - point[i].second;ll lk1 = point[l].first - point[k].first;ll lk2 = point[l].second - point[k].second;ll kj1 = point[k].first - point[j].first;ll kj2 = point[k].second - point[j].second;ll add = 0;if(cross({ji1, ji2}, {lk1, lk2}) == 0) add = 1;ll kji = cross({ji1, ji2}, {kj1, kj2});ll lkj = cross({kj1, kj2}, {lk1, lk2});if(kji * lkj <= 0) add = 1;ll lqk = cross({ji1, ji2}, {lk1 - ji1, lk2 - ji2});if(kji * lqk <= 0) add = 1;chmin(dp[f(bit, j, k, l, 0)], dp[f((bit) ^ (1 << l), i, j, k, 0)] + 1);chmin(dp[f(bit, j, k, l, 0)], dp[f((bit) ^ (1 << l), i, j, k, 1)] + 1);chmin(dp[f(bit, j, k, l, 1)], dp[f((bit) ^ (1 << l), i, j, k, 0)] + add);}}}}}ll ans = inf;fori(i, n) fori(j, n) fori(k, n){chmin(ans, dp[f((1 << n) - 1, i, j, k, 0)]);chmin(ans, dp[f((1 << n) - 1, i, j, k, 1)]);}print(ans);}int main(){cin.tie(0)->sync_with_stdio(0);int t;t = 1;// cin >> t;while(t--) solve();return 0;}