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