1007 vector matching

์•Œ๊ณ ๋ฆฌ์ฆ˜

1. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค ๋ณ„๋กœ ๋ชจ๋“  x์ขŒํ‘œ์™€ y์ขŒํ‘œ๋ฅผ ๋”ํ•จ
2. n/2๊ฐœ์˜ ์ ์„ ๊ณ ๋ฅด๊ณ , ๊ทธ ๊ณ ๋ฅธ ์ ๋“ค์˜ ๋ชจ๋“  x์ขŒํ‘œ์™€ y์ขŒํ‘œ๋ฅผ ๋”ํ•จ
3. 1์—์„œ ๊ตฌํ•œ x,y ์— 2์—์„œ ๊ตฌํ•œ x,y๋ฅผ 2๊ณฑํ•˜๊ณ  ๋บŒ. (sumOfEveryX - 2*sumOfChoosedX)
4. 3.์—์„œ ๊ตฌํ•œ ๋ฒกํ„ฐ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•œ ํ›„ ๋ฐ˜ํ™˜. ๋ฐ˜ํ™˜ ๋ฐ›์€ ๊ณณ์€ ์ตœ์†Ÿ๊ฐ’์„ ๋‹ค์‹œ ๋ฐ˜ํ™˜

์„ค๋ช…

๋“ค์–ด์˜ค๋Š” ์ ๋“ค์ด ์ง์ˆ˜์ด๊ณ , ๋‘๊ฐœ์”ฉ ์ง ์ง€์–ด์ค€๋‹ค๋ฉด ๋ฒกํ„ฐ๋ฅผ ๊ตฌํ–ˆ์„ ๋•Œ ๋ฐ˜์€ ๋”ํ•˜๋Š” ํ˜•ํƒœ์ด๊ณ , ๋ฐ˜์€ ๋นผ๋Š” ํ˜•ํƒœ์ด๋‹ค.
๋”ฐ๋ผ์„œ ๋นผ์ค„ ๋ฐ˜์„ ๊ณ ๋ฅด๊ณ , ์ „์ฒด X์˜ ํ•ฉ์—์„œ ๋นผ๋ฉด ๋จ. ๊ทผ๋ฐ ์ „์ฒด X์˜ ํ•ฉ์ด๋ฏ€๋กœ ๋นผ์ค„ ๋ฐ˜์€ ๋‘๋ฐฐ๋กœ ๊ณฑํ•˜๊ณ  ๋นผ์•ผํ•œ๋‹ค.

์‚ฝ์งˆ๊ณผ์ •

์ฒ˜์Œ์— ๋ชจ๋“  ์Œ์„ ์ง€์–ด์ฃผ๊ณ , ๋ชจ๋“  ๋ฐฉํ–ฅ์„ ๊ฒ€์‚ฌํ•˜์—ฌ ๊ธธ์ด๋ฅผ ๊ตฌํ•ด๋„ ์‹œ๊ฐ„์•ˆ์— ๋  ์ค„ ์•Œ์•˜์Œ
-> ํ•˜์ง€๋งŒ ๊ณ„์‚ฐํ•ด๋ณด๋‹ˆ ๋ฏธ์นœ๋“ฏ์ด ์‹œ๊ฐ„์ด ๋งŽ์ด ๊ฑธ๋ฆผ
-> ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์œผ๋กœ ๋น ๋ฅด๊ฒŒ ์ „ํ™˜ํ–ˆ์–ด์•ผํ–ˆ๋‹ค

๊ทธ๋ฆฌ๊ณ  ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š”๋ฐ ๋จธ๋ฆฌ๋กœ๋งŒ ํ‘ธ๋Š” ๋ฒ„๋ฆ‡์ด ๋“ค์—ˆ๋Š”๋ฐ ์ด๊ฑธ ๊ณ ์น˜๊ณ  ์ด๋Ÿฐ ์ˆ˜ํ•™์ ์ธ ๋ฌธ์ œ๋Š” ์ ์œผ๋ฉด์„œ ํ’€์–ด๋ณด์ž.

๊ตํ›ˆ

1. ์ƒ๊ฐ๋‚œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์žˆ์œผ๋ฉด ํ•œ๋ฒˆ ๋ณต์žก๋„ ๊ณ„์‚ฐํ•ด๋ณด์ž
2. ์ˆ˜ํ•™์ ์ธ ๋ฌธ์ œ์˜ ๊ฒฝ์šฐ ์‹์„ ์ ์œผ๋ฉด์„œ ํ’€์–ด๋ณด์ž.

์ฝ”๋“œ

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef struct Point {
	int x;
	int y;
} Point;
 
vector<vector<Point>> tc;
vector<Point> currentPoint;
int sumOfEveryX, sumOfEveryY;
 
void generateTc();
long double solveSingleTC(vector<int> choosed, int deep);
 
int main() {
	int numOfTc;
	cin >> numOfTc;
	for (int i = 0; i < numOfTc; i++) {
		int numOfPoint;
		cin >> numOfPoint;
		vector<Point> tempPoint;
		for (int j = 0; j < numOfPoint; j++) {
			int x, y;
			cin >> x >> y;
			tempPoint.push_back({ x, y });
		}
		tc.push_back(tempPoint);
	}
	generateTc();
}
 
void generateTc() {
	for (int i = 0; i < tc.size(); i++) {
		currentPoint = tc[i];
		sumOfEveryX = 0;
		sumOfEveryY = 0;
		for (int j = 0; j < currentPoint.size(); j++) {
			sumOfEveryX += currentPoint[j].x;
			sumOfEveryY += currentPoint[j].y;
		}
		vector<int> choosed;
		cout << "test" << endl;
		cout.precision(50);
		cout << solveSingleTC(choosed, 0) << endl;
	}
}
 
long double solveSingleTC(vector<int> choosed, int deep) {
	if (choosed.size() == currentPoint.size() / 2) {
		long long sumOfChoosedX = 0;
		long long sumOfChoosedY = 0;
		for (int i = 0; i < choosed.size(); i++) {
			sumOfChoosedX += currentPoint[choosed[i]].x;
			sumOfChoosedY += currentPoint[choosed[i]].y;
		}
		long long length = (sumOfEveryX - 2 * sumOfChoosedX) * (sumOfEveryX - 2 * sumOfChoosedX) +
							(sumOfEveryY - 2 * sumOfChoosedY) * (sumOfEveryY - 2 * sumOfChoosedY);
		return sqrt(length);
	}
	else if (currentPoint.size() - deep < (currentPoint.size() / 2) - choosed.size())
		return 2000000000;
 
	long double a = solveSingleTC(choosed, deep + 1);
	choosed.push_back(deep);
	long double b = solveSingleTC(choosed, deep + 1);
	return a < b ? a : b;
}