結果
| 問題 | No.2180 Comprehensive Line Segments |
| ユーザー |
 MasKoaTS
|
| 提出日時 | 2022-11-28 18:40:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,664 bytes |
| コンパイル時間 | 3,414 ms |
| コンパイル使用メモリ | 243,472 KB |
| 最終ジャッジ日時 | 2025-02-09 01:52:17 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 MLE * 1 |
| other | AC * 11 WA * 1 TLE * 4 MLE * 9 |
ソースコード
#include <bits/stdc++.h>#define rep(i, l, n) for (int i = (l); i < (n); i++)using namespace std;using ll = long long;template <class T> using V = vector<T>;struct Fraction {ll num;ll den;static 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;}static ll lcm(ll x, ll y) {ll g = gcd(x, y);return x / g * y;}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;}static Fraction parsePositive(Fraction x) {if (x.num < 0) {return -x;}return x;}Fraction operator+(void) const {return *this;}Fraction operator-(void) const {return Fraction() - (*this);}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();struct Vector2 {Fraction x;Fraction y;Vector2(void) {x = zero;y = zero;}Vector2(Fraction x, Fraction y) {this->x = x;this->y = y;}static Vector2 normalize(Vector2 v) {assert(v.x != zero or v.y != zero);Fraction norm = v.x * v.x + v.y * v.y;return Vector2(v.x * Fraction::parsePositive(v.x) / norm, v.y * Fraction::parsePositive(v.y) / norm);}Vector2 operator+(const Vector2 other) const {return Vector2(other.x + this->x, other.y - this->y);}Vector2 operator-(const Vector2 other) const {return Vector2(other.x - this->x, other.y - this->y);}Fraction 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);}};const Vector2 zeroVector = 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) {assert(one != 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(-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);}/** 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> point_mp = {};int point_num = 0;for (Vector2& p : P) {point_mp[p] = point_num;point_num++;}// 有り得る直線を調べて番号付けmap<Line, int> line_mp = {};int line_num = 0;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 (line_mp.find(l) != line_mp.end()) {continue;}line_mp[l] = line_num;line_num++;vec.push_back(l);}}// 有り得る交点を調べて番号付けrep(i, 0, line_num - 1) {rep(j, i + 1, line_num) {Line l1 = vec[i], l2 = vec[j];Vector2* p = calcIntersection(l1, l2);if (p == nullptr or point_mp.find(*p) != point_mp.end()) {continue;}P.push_back(*p);point_mp[*p] = point_num;point_num++;}}//任意の2点について、2点から構成されるベクトルを調べて正規化V<V<Vector2> > vectors(point_num, V<Vector2>(point_num, zeroVector));rep(i, 0, point_num - 1) {rep(j, i + 1, point_num) {if (line_mp.find(calcLine(P[i], P[j])) == line_mp.end()) {continue;}vectors[i][j] = Vector2::normalize(P[j] - P[i]);vectors[j][i] = Vector2::normalize(P[i] - P[j]);}}// グラフ探索V<V<V<int> > > dp(1 << N, V<V<int> >(point_num, V<int>(point_num, N)));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 = N;while (que.empty() == false) {V<int> vec = que.front(); que.pop_front();int c_now = vec[0], b_now = vec[1], v_prev = vec[2], v_now = vec[3];if (c_now > dp[b_now][v_prev][v_now]) {continue;}if (b_now == goal) {ans = c_now;break;}rep(v_next, 0, point_num) {if (v_now == v_next or min(v_now, v_next) >= N or vectors[v_now][v_next] == zeroVector) {continue;}int b_next = (v_next < N) ? (b_now | (1 << v_next)) : b_now;int c_next = c_now;if (v_prev == v_now or vectors[v_prev][v_now] != vectors[v_now][v_next]) {c_next++;}if (c_next >= dp[b_next][v_now][v_next]) {continue;}dp[b_next][v_now][v_next] = c_next;if (c_next == c_now) {que.push_front({ c_next, b_next, v_now, v_next });}else {que.push_back({ c_next, b_next, v_now, v_next });}}}cout << ans << endl;return 0;}