結果

問題 No.2180 Comprehensive Line Segments
コンテスト
ユーザー MasKoaTS
提出日時 2022-10-11 18:42:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,411 bytes
コンパイル時間 2,428 ms
コンパイル使用メモリ 209,160 KB
最終ジャッジ日時 2025-02-08 01:26:34
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other AC * 9 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, l, n) for (int i = (l); i < (n); i++)
#define abs(x) (((x) < 0) ? -(x) : (x))
#define all(x) x.begin(), x.end()
#define last(v) v[v.size() - 1]
#define inf 1000000000
#define INF Fraction(1000000000000000000ll, 1ll)
using namespace std;
using ll = long long;
template <class T>	using V = vector<T>;

inline bool isContinuousBit(int bit) {
	bool flag = false;
	while (bit) {
		if ((bit & 3) == 3) {
			flag = true;
			break;
		}
		bit >>= 1;
	}
	return flag;
}

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);
	}
};

inline int sgn(Fraction x) {
	if (Fraction() < x) {
		return 1;
	}
	if (x < Fraction()) {
		return -1;
	}
	return 0;
}


struct Vector2 {
	Fraction x;
	Fraction y;

	Vector2(void) {
		x = Fraction();
		y = Fraction();
	}

	Vector2(Fraction x, Fraction y) {
		this->x = x;
		this->y = y;
	}

	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);
	}

	bool operator<(const Vector2 other) const {
		return tie(this->x, this->y) < tie(other.x, other.y);
	}

	bool isNull(void) {
		return (this->x == INF and this->y == INF);
	}

	void show(void) {
		cout << '(' << this->x.num << " / " << this->x.den << ", " << this->y.num << " / " << this->y.den << ')' << endl;
	}
};

inline bool isSmaeInclination(Vector2 one, Vector2 other) {
	if (one.x == Fraction()) {
		return (other.x == Fraction() and Fraction() < one.y / other.y);
	}
	Fraction a = other.x / one.x;
	return (a * one.y == other.y and Fraction() < a);
}

inline Fraction calcOuterProduct(Vector2 one, Vector2 other) {
	return one.x * other.y - one.y * other.x;
}


/*
* 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;
	}

	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 = { p[1] - p[0] };
		rep(i, 1, N - 1) {
			Vector2 v = p[i + 1] - p[i];
			if (isSmaeInclination(last(vec), v)) {
				continue;
			}
			if (calcOuterProduct(last(vec), v) == Fraction()) {
				flag = true;
				break;
			}
			vec.push_back(v);
		}
		if (flag) {
			continue;
		}

		int M = vec.size();
		if (M <= 2) {
			ans = min(ans, M);
			continue;
		}
		
		rep(i, 0, 1 << (M - 2)) {
			if (isContinuousBit(i)) {
				continue;
			}
			int bit = i << 1;
			int cnt = M;
			rep(j, 1, M - 1) {
				if (((bit >> j) & 1) == 0) {
					continue;
				}
				Vector2 v1 = vec[j - 1], v2 = vec[j], v3 = vec[j + 1];
				int s1 = sgn(calcOuterProduct(v1, v2));
				int s2 = sgn(calcOuterProduct(v2, v3));
				int s3 = sgn(calcOuterProduct(v1, v3));
				if (s1 == s2 and s2 == s3) {
					cnt--;
				}
			}
			ans = min(ans, cnt);
		}
	} while (next_permutation(all(num)));

	cout << ans << endl;

	return 0;
}
0