글 읽기 - 어떻게 더 시간을 줄일 수 있을까요??

jinhan814 3년 전 0

외적을 이용해서 O(nC3 * 2^3 * n) = O(n^4)에 구현했는데 시간초과가 나네요. 브루트포스가 정해인 거 같은데 여기서 어떻게 더 시간을 줄일 수 있는지 궁금합니다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

typedef long long ll;

struct Point {
	ll x, y, z;
	Point() : x(0), y(0), z(0) {}
	Point(ll x, ll y, ll z) : x(x), y(y), z(z) {}
};

Point operator + (const Point& a, const Point& b) {
	return Point(a.x + b.x, a.y + b.y, a.z + b.z);
}

struct Vector {
	ll x, y, z;
	Vector() : x(0), y(0), z(0) {}
	Vector(ll x, ll y, ll z) : x(x), y(y), z(z) {}
	Vector(Point st, Point en) : x(en.x - st.x), y(en.y - st.y), z(en.z - st.z) {}
	int norm() { return x * x + y * y + z * z; }
};

Vector operator + (const Vector& a, const Vector& b) {
	return Vector(a.x + b.x, a.y + b.y, a.z + b.z);
}

Vector operator - (const Vector& a, const Vector& b) {
	return Vector(a.x - b.x, a.y - b.y, a.z - b.z);
}

//inner product;
int operator * (const Vector& a, const Vector& b) {
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

//outer product;
Vector operator / (const Vector& a, const Vector& b) {
	return Vector(a.y * b.z - b.y * a.z, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);
}

istream& operator >> (istream& in, Point& p) {
	in >> p.x >> p.y >> p.z;
	return in;
}

ostream& operator << (ostream& out, Vector& v) {
	out << v.x << ' ' << v.y << ' ' << v.z << '\n';
	return out;
}

bool w[101], check[101];
void dfs(int& n, double& ans, vector<Point>& v, int depth, int idx) {
	if (depth == 3) {
		for (int c = 0; c < 8; c++) {
			vector<Point> temp;
			for (int i = 0; i < n; i++) if (w[i]) {
				temp.push_back(v[i]);
			}
			Vector v1(temp[0], temp[1]), v2(temp[0], temp[2]);
			Vector normal = v1 / v2;
			for (int i = 0, cnt = 0; i < n; i++) {
				if (w[i]) check[i] = c & (1 << cnt++);
				else {
					Vector v3(v[i], temp[0]);
					check[i] = normal * v3 > 0;
				}
			}
			int _cnt1 = 0, _cnt2 = 0;
			Point cnt1, cnt2;
			for (int i = 0; i < n; i++) {
				if (check[i]) cnt1 = cnt1 + v[i], _cnt1++;
				else cnt2 = cnt2 + v[i], _cnt2++;
			}
			double cur = 0;
			double r1 = double(cnt1.x) / _cnt1;
			double g1 = double(cnt1.y) / _cnt1;
			double b1 = double(cnt1.z) / _cnt1;
			double r2 = double(cnt2.x) / _cnt2;
			double g2 = double(cnt2.y) / _cnt2;
			double b2 = double(cnt2.z) / _cnt2;
			for (int i = 0; i < n; i++) {
				if (check[i]) {
					cur += (r1 - v[i].x) * (r1 - v[i].x);
					cur += (g1 - v[i].y) * (g1 - v[i].y);
					cur += (b1 - v[i].z) * (b1 - v[i].z);
				}
				else {
					cur += (r2 - v[i].x) * (r2 - v[i].x);
					cur += (g2 - v[i].y) * (g2 - v[i].y);
					cur += (b2 - v[i].z) * (b2 - v[i].z);
				}
			}
			ans = min(ans, cur);
		}
	}
	for (int i = idx; i < n; i++) {
		if (w[i]) continue;
		w[i] = 1;
		dfs(n, ans, v, depth + 1, i + 1);
		w[i] = 0;
	}
}

int main() {
	fastio;
	cout << fixed << setprecision(6);
	int n, k; cin >> n >> k;
	vector<Point> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	if (k & 1) {
		/* k == 1일 때는 따로 처리하기 */
		Point sum;
		for (int i = 0; i < n; i++) {
			sum = sum + v[i];
		}
		double ans = 0;
		double r = double(sum.x) / n;
		double g = double(sum.y) / n;
		double b = double(sum.z) / n;
		for (int i = 0; i < n; i++) {
			ans += (r - v[i].x) * (r - v[i].x);
			ans += (g - v[i].y) * (g - v[i].y);
			ans += (b - v[i].z) * (b - v[i].z);
		}
		cout << ans << '\n';
		return 0;
	}
	if (n < 3) {
		/* n이 3 미만일 때는 따로 처리하기 */
		cout << 0 << '\n';
		return 0;
	}
	double ans = 1e18;
	dfs(n, ans, v, 0, 0);
	cout << ans << '\n';
}

문제를 푼 적도 없고 풀이도 잘 모르지만, 문제에서 주어진 식은 이른바 분산을 계산하고 있습니다. 그리고 분산을 곧이곧대로 구하지 않고 더 쉽게(?) 구하는 공식은 검색하면 잘 나옵니다. 그 공식을 사용하면 nC3 개의 각 평면에 대해서 83번 루프의 O(n)번 실수 계산을 하지 않고 정수를 사용해서 구하면 실수 계산을 줄이니까 좀 시간이 덜 걸릴 것 같습니다. 또 그 공식을 잘 알아보면 각 평면에 대해서 3개의 점이 어느 쪽에 들어가는지에 따라 나뉘는 8개의 경우가 겹치는 계산이 많이 나와서 줄어들 겁니다 아마.

jinhan814 3년 전 0

알려주신대로 구현하니 AC받았습니다. 감사합니다 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어떻게 더 시간을 줄일 수 있을까요??

jinhan814 3년 전 0

sait2000 3년 전 3

jinhan814 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말