結果

問題 No.2180 Comprehensive Line Segments
ユーザー MasKoaTSMasKoaTS
提出日時 2022-11-28 18:40:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 6,664 bytes
コンパイル時間 3,856 ms
コンパイル使用メモリ 254,084 KB
実行使用メモリ 814,720 KB
最終ジャッジ日時 2024-04-28 10:35:22
合計ジャッジ時間 8,040 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 MLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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個のときは必ず答え1
	if (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;
}
0