#include #include #include #include #include #include #include #include #include using namespace std; struct Vector { long long int x, y; long long int GetSquareDistanceTo(Vector vec) { return pow(vec.x - x, 2) + pow(vec.y - y, 2); } long double GetDistance() { return sqrt(GetSquareDistanceTo({ 0, 0 })); } Vector operator-(Vector vec) { return { x - vec.x, y - vec.y }; } Vector operator+(Vector vec) { return { x + vec.x, y + vec.y }; } Vector& operator+=(Vector vec) { *this = *this + vec; return *this; } }; void Rec(vector points, int t, int index, vector>& pointGroups, vector tmpGroup) { if (t == 0) { pointGroups.push_back(tmpGroup); return; } t -= 1; for (int i = index + 1; i < points.size() - t; i++) { tmpGroup.push_back(points[i]); Rec(points, t, i, pointGroups, tmpGroup); tmpGroup.pop_back(); } } long double GetMinDistanceOfVectorWithSum(vector points) { vector> pointGroups; vector tmpGroup; Rec(points, points.size() / 2, -1, pointGroups, tmpGroup); Vector sum = { 0, 0 }; for (int i = 0; i < points.size(); i++) { sum += points[i]; } vector values; for (int i = 0; i < pointGroups.size(); i++) { Vector tmpSum = { 0, 0 }; for (int j = 0; j < pointGroups[i].size(); j++) tmpSum += pointGroups[i][j]; values.push_back(tmpSum - (sum - tmpSum)); } Vector min = *min_element(values.begin(), values.end(), [](Vector a, Vector b) { return a.GetSquareDistanceTo({ 0, 0 }) < b.GetSquareDistanceTo({ 0, 0 }); }); return min.GetDistance(); } int main() { int t; cin >> t; vector results; for (int i = 0; i < t; i++) { int k; cin >> k; vector points; for (int j = 0; j < k; j++) { int x, y; cin >> x >> y; points.push_back({ x, y }); } long double result = LLONG_MAX; long double min = GetMinDistanceOfVectorWithSum(points); result = min < result ? min : result; results.push_back(result); } for (int i = 0; i < results.size(); i++) printf("%.7lf\n", results[i]); return 0; }

코드 #531