結果
| 問題 | No.2180 Comprehensive Line Segments |
| ユーザー |
 MasKoaTS
|
| 提出日時 | 2022-10-12 21:32:03 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,948 bytes |
| コンパイル時間 | 3,176 ms |
| コンパイル使用メモリ | 242,860 KB |
| 最終ジャッジ日時 | 2025-02-08 02:14:14 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 MLE * 2 |
| other | AC * 10 WA * 1 TLE * 6 MLE * 8 |
ソースコード
#include <bits/stdc++.h>#define rep(i, l, n) for (int i = (l); i < (n); i++)#define inf 1000000000using namespace std;using ll = long long;template <class T> using V = vector<T>;inline ll gcd(ll x, ll y) {x = abs(x); y = abs(y);while (y != 0) {ll r = x % y;x = y;y = r;}return x;}inline ll lcm(ll x, ll y) {ll g = gcd(x, y);return x / g * y;}struct Fraction {ll num;ll den;Fraction(void) {num = 0ll;den = 1ll;}Fraction(ll num, ll den) {assert(den != 0);ll g = gcd(num, den);num /= g;den /= g;if (den < 0) {num = -num;den = -den;}this->num = num;this->den = den;}Fraction operator+(const Fraction other) const {ll l = lcm(this->den, other.den);ll a = l / this->den;ll b = l / other.den;ll nnum = this->num * a + other.num * b;ll nden = l;return Fraction(nnum, nden);}Fraction operator-(const Fraction other) const {Fraction f = Fraction(-other.num, other.den);return (*this) + f;}Fraction operator*(const Fraction other) const {ll nnum = this->num * other.num;ll nden = this->den * other.den;return Fraction(nnum, nden);}Fraction operator/(const Fraction other) const {Fraction f = Fraction(other.den, other.num);return (*this) * f;}bool operator<(const Fraction other) const {ll l = lcm(this->den, other.den);ll a = l / this->den;ll b = l / other.den;return (this->num * a < other.num* b);}bool operator==(const Fraction other) const {ll l = lcm(this->den, other.den);ll a = l / this->den;ll b = l / other.den;return (this->num * a == other.num * b);}bool operator!=(const Fraction other) const {return (((*this) == other) == false);}};const Fraction zero = Fraction();inline Fraction abs_frac(Fraction x) {return ((x < zero) ? zero - x : x);}struct Vector2 {Fraction x;Fraction y;Vector2(void) {x = zero;y = zero;}Vector2(Fraction x, Fraction y) {this->x = x;this->y = y;}Vector2 operator-(const Vector2 other) const {return Vector2(other.x - this->x, other.y - this->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);}bool operator!=(const Vector2 other) const {return tie(this->x, this->y) != tie(other.x, other.y);}};const Vector2 zero_vector = Vector2();struct Line {Fraction a;Fraction b;Fraction c;Line(void) {a = zero;b = zero;c = zero;}Line(Fraction a, Fraction b, Fraction c) {this->a = a;this->b = b;this->c = c;}bool operator<(const Line other) const {return tie(this->a, this->b, this->c) < tie(other.a, other.b, other.c);}};Line calcLine(Vector2 one, Vector2 other) {Fraction x1 = one.x, y1 = one.y;Fraction x2 = other.x, y2 = other.y;if (x1 == x2) {return Line(Fraction(1ll, 1ll), Fraction(0ll, 1ll), x1);}Fraction a = (y1 - y2) / (x1 - x2);Fraction c = y1 - a * x1;return Line(zero - a, Fraction(1ll, 1ll), c);}Vector2* calcIntersection(Line one, Line other) {Fraction p = one.a * other.b - other.a * one.b;if (p == zero) {return nullptr;}Fraction q = other.b * one.c - one.b * other.c;Fraction x = q / p;Fraction y = (one.b == zero) ? ((other.c - other.a * x) / other.b) : ((one.c - one.a * x) / one.b);return new Vector2(x, y);}Vector2 normalize_vector(Vector2 v) {assert(v.x != zero or v.y != zero);Fraction norm = v.x * v.x + v.y * v.y;return Vector2(v.x * abs_frac(v.x) / norm, v.y * abs_frac(v.y) / norm);}/** Main Code*/int main(void) {// 入力int N; cin >> N;V<Vector2> P(N);rep(i, 0, N) {ll x, y; cin >> x >> y;P[i] = { Fraction(x,1ll),Fraction(y,1ll) };}// 点が1個のときは必ず答え1if (N == 1) {cout << 1 << endl;return 0;}// 各点に番号付けmap<Vector2, int> ph = {};int pt_id = 0;for (Vector2& p : P) {ph[p] = pt_id;pt_id++;}// 有り得る直線を調べて番号付けint ln_id = 0;map<Line, int> lh = {};V<Line> vec = {};rep(i, 0, N - 1) {rep(j, i + 1, N) {Vector2 p1 = P[i], p2 = P[j];Line l = calcLine(p1, p2);if (lh.find(l) != lh.end()) {continue;}lh[l] = ln_id;ln_id++;vec.push_back(l);}}// 有り得る交点を調べて番号付けrep(i, 0, ln_id - 1) {rep(j, i + 1, ln_id) {Line l1 = vec[i], l2 = vec[j];Vector2* p = calcIntersection(l1, l2);if (p == nullptr or ph.find(*p) != ph.end()) {continue;}P.push_back(*p);ph[*p] = pt_id;pt_id++;}}//任意の2点について、2点から構成されるベクトルを調べて正規化V<V<Vector2> > vectors(pt_id, V<Vector2>(pt_id, zero_vector));rep(i, 0, pt_id - 1) {rep(j, i + 1, pt_id) {if (lh.find(calcLine(P[i], P[j])) == lh.end()) {continue;}vectors[i][j] = normalize_vector(P[j] - P[i]);vectors[j][i] = normalize_vector(P[i] - P[j]);}}// グラフ探索V<V<V<int> > > dp(1 << N, V<V<int> >(pt_id, V<int>(pt_id, inf)));deque<V<int> > que = {};rep(i, 0, N) {que.push_back({ 0, 1 << i, i, i });dp[1 << i][i][i] = 0;}int goal = (1 << N) - 1;int ans = inf;int cnt = 0;while (que.empty() == false) {V<int> vec = que.front(); que.pop_front();int c = vec[0], b = vec[1], lv = vec[2], v = vec[3];if (c > dp[b][lv][v]) {continue;}if (b == goal) {ans = c;break;}rep(nv, 0, pt_id) {if (v == nv or vectors[v][nv] == zero_vector) {continue;}int nb = (nv < N) ? (b | (1 << nv)) : b;int nc = c;if (lv == v or vectors[lv][v] != vectors[v][nv]) {nc++;}if (nc >= dp[nb][v][nv]) {continue;}dp[nb][v][nv] = nc;if (nc == c) {que.push_front({ nc, nb, v, nv });}else {que.push_back({ nc, nb, v, nv });}}}cout << ans << endl;return 0;}