結果

問題 No.2180 Comprehensive Line Segments
ユーザー MasKoaTSMasKoaTS
提出日時 2022-09-11 16:19:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 3,910 bytes
コンパイル時間 3,353 ms
コンパイル使用メモリ 245,404 KB
実行使用メモリ 818,176 KB
最終ジャッジ日時 2024-11-17 00:43:26
合計ジャッジ時間 34,656 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
7,424 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 MLE -
testcase_04 AC 27 ms
5,120 KB
testcase_05 AC 2 ms
5,120 KB
testcase_06 AC 3 ms
5,120 KB
testcase_07 AC 3 ms
5,120 KB
testcase_08 AC 3 ms
5,120 KB
testcase_09 AC 75 ms
39,040 KB
testcase_10 MLE -
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
testcase_14 MLE -
testcase_15 MLE -
testcase_16 MLE -
testcase_17 MLE -
testcase_18 MLE -
testcase_19 MLE -
testcase_20 AC 11 ms
5,504 KB
testcase_21 MLE -
testcase_22 WA -
testcase_23 AC 1,881 ms
375,168 KB
testcase_24 AC 319 ms
83,328 KB
testcase_25 MLE -
testcase_26 MLE -
testcase_27 WA -
testcase_28 AC 1,151 ms
422,624 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, l, n) for (int i = (l); i < (n); i++)
#define inf 1000000000
#define INF 1e9
using namespace std;
template <class T>	using V = vector<T>;

bool equal(double a, double b) {
	return (fabs(a - b) < 1e-10);
}

struct Point {
	double x;
	double y;

	Point(void) {
		x = 0.0;
		y = 0.0;
	}

	Point(double x, double y) {
		this->x = x;
		this->y = y;
	}

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

	bool operator==(const Point other) const {
		return (equal(this->x, other.x) and equal(this->y, other.y));
	}

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

struct Line {
	double a;
	double b;
	double c;

	Line(void) {
		a = 1.0;
		b = 1.0;
		c = 1.0;
	}

	Line(double a, double b, double 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);
	}

	bool operator==(const Line other) const {
		return (equal(this->a, other.a) and equal(this->b, other.b) and equal(this->c, other.c));
	}
};

Line calcLine(Point one, Point other) {
	double x1 = one.x, y1 = one.y;
	double x2 = other.x, y2 = other.y;
	if (x1 == x2) {
		return Line(1.0, 0.0, x1);
	}
	double a = (y1 - y2) / (x1 - x2);
	double c = y1 - a * x1;
	return Line(-a, 1.0, c);
}

Point intersection(Line one, Line other) {
	double p = one.a * other.b - other.a * one.b;
	if (equal(p, 0.0)) {
		return Point(INF, INF);
	}
	double q = other.b * one.c - one.b * other.c;
	double x = q / p;
	double y = (equal(one.b, 0.0)) ? ((other.c - other.a * x) / other.b) : ((one.c - one.a * x) / one.b);
	return Point(x, y);
}


/*
* Main Code
*/

int main(void) {
	int N;	cin >> N;
	V<Point> P(N);
	rep(i, 0, N) {
		double x, y;	cin >> x >> y;
		P[i] = { x,y };
	}

	if (N == 1) {
		cout << 1 << endl;
		return 0;
	}

	map<Point, int> ph = {};
	int pt_id = 0;
	for (Point 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, 1, N) {
			Point 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, 1, ln_id) {
			Line l1 = vec[i], l2 = vec[j];
			Point p = intersection(l1, l2);
			if (p.isNull() or ph.find(p) != ph.end()) {
				continue;
			}
			P.push_back(p);
			ph[p] = pt_id;
			pt_id++;
		}
	}

	V<V<pair<int, int> > > dir_lis(pt_id, V<pair<int, int> >(pt_id, pair<int, int>({ inf,0 })));
	rep(i, 0, pt_id - 1) {
		rep(j, 1, pt_id) {
			Point p1 = P[i], p2 = P[j];
			Line l = calcLine(p1, p2);
			if (lh.find(l) == lh.end()) {
				continue;
			}
			dir_lis[i][j] = { lh[l], (p1 < p2) };
			dir_lis[j][i] = { lh[l], (p2 < p1) };
		}
	}

	V<V<V<V<int> > > > dp(1 << N, V<V<V<int> > >(pt_id, V<V<int> >(ln_id + 1, V<int>(2, inf))));
	deque<V<int> > que = {};
	rep(i, 0, N) {
		que.push_back({ 0, 1 << i, i, ln_id, 0 });
		dp[1 << i][i][ln_id][0] = 0;
	}
	int goal = (1 << N) - 1;
	int ans = inf;
	int cnt = 0;
	while (que.empty() == false) {
		//cout << que.size() << endl;
		V<int> vec = que.front();	que.pop_front();
		int c = vec[0], b = vec[1], v = vec[2], l = vec[3], a = vec[4];
		if (l != ln_id and c > dp[b][v][l][a]) {
			continue;
		}
		if (b == goal) {
			ans = c;
			break;
		}
		rep(nv, 0, pt_id) {
			int nb = (nv < N) ? (b | (1 << nv)) : b;
			if (dir_lis[v][nv].first == inf) {
				continue;
			}
			int nl = dir_lis[v][nv].first, na = dir_lis[v][nv].second;
			int nc = c;
			if (l == ln_id or l != nl or a != na) {
				nc++;
			}
			if (nc >= dp[nb][nv][nl][na]) {
				continue;
			}
			dp[nb][nv][nl][na] = nc;
			if (nc == c) {
				que.push_front({ nc, nb, nv, nl, na });
			}
			else {
				que.push_back({ nc, nb, nv, nl, na });
			}
		}
	}
	cout << ans << endl;

	return 0;
}
0