結果
| 問題 | No.2180 Comprehensive Line Segments |
| ユーザー |
 MasKoaTS
|
| 提出日時 | 2022-11-28 19:59:38 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,603 bytes |
| コンパイル時間 | 2,039 ms |
| コンパイル使用メモリ | 214,016 KB |
| 最終ジャッジ日時 | 2025-02-09 01:54:11 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 TLE * 1 |
| other | AC * 9 TLE * 16 |
ソースコード
#include <bits/stdc++.h>#define rep(i, l, n) for (int i = (l); i < (n); i++)#define all(x) x.begin(), x.end()#define last(v) v[v.size() - 1]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();int sgn(Fraction x) {if (zero < x) {return 1;}if (x < zero) {return -1;}return 0;}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();/** 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) };}if (N == 1) {cout << 1 << endl;return 0;}V<V<Vector2> > vectors(N, V<Vector2>(N));rep(i, 0, N - 1) {rep(j, i + 1, N) {vectors[i][j] = Vector2::normalize(P[j] - P[i]);vectors[j][i] = Vector2::normalize(P[i] - P[j]);}}int ans = N;V<int> num(N);rep(i, 0, N) {num[i] = i;}do {bool flag = false;V<Vector2> p(N);rep(i, 0, N) {p[i] = P[num[i]];}V<Vector2> vec = { vectors[num[0]][num[1]] };rep(i, 1, N - 1) {Vector2 v = vectors[num[i]][num[i + 1]];if (last(vec) == v) {continue;}if (last(vec) * v == zero) {flag = true;break;}vec.push_back(v);}if (flag) {continue;}int M = vec.size();if (M <= 2) {ans = min(ans, M);continue;}V<pair<int, int> > dp(M - 1, { -1,-1 });dp[0].first = 0;rep(i, 1, M - 1) {Vector2 v1 = vec[i - 1], v2 = vec[i], v3 = vec[i + 1];int s1 = sgn(v1 * v2), s2 = sgn(v2 * v3), s3 = sgn(v1 * v3);if (s1 == s2 and s2 == s3) {dp[i].second = dp[i - 1].first + 1;}dp[i].first = max(dp[i - 1].first, dp[i - 1].second);}ans = min(ans, M - max(dp[M - 2].first, dp[M - 2].second));} while (next_permutation(all(num)));cout << ans << endl;return 0;}