diff options
| -rw-r--r-- | PlaygroundCpp/.settings/language.settings.xml | 4 | ||||
| -rw-r--r-- | PlaygroundCpp/Sources/Playground.cpp | 218 |
2 files changed, 148 insertions, 74 deletions
diff --git a/PlaygroundCpp/.settings/language.settings.xml b/PlaygroundCpp/.settings/language.settings.xml index aa6e0c9..1410d72 100644 --- a/PlaygroundCpp/.settings/language.settings.xml +++ b/PlaygroundCpp/.settings/language.settings.xml @@ -5,7 +5,7 @@ <provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/> <provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/> <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939321890483387581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> <language-scope id="org.eclipse.cdt.core.g++"/> </provider> @@ -16,7 +16,7 @@ <provider copy-of="extension" id="org.eclipse.cdt.ui.UserLanguageSettingsProvider"/> <provider-reference id="org.eclipse.cdt.core.ReferencedProjectsLanguageSettingsProvider" ref="shared-provider"/> <provider-reference id="org.eclipse.cdt.managedbuilder.core.MBSLanguageSettingsProvider" ref="shared-provider"/> - <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939321890483387581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> + <provider class="org.eclipse.cdt.managedbuilder.language.settings.providers.GCCBuiltinSpecsDetector" console="false" env-hash="-939090329124603581" id="org.eclipse.cdt.managedbuilder.core.GCCBuiltinSpecsDetector" keep-relative-paths="false" name="CDT GCC Built-in Compiler Settings" parameter="${COMMAND} ${FLAGS} -E -P -v -dD "${INPUTS}"" prefer-non-shared="true"> <language-scope id="org.eclipse.cdt.core.gcc"/> <language-scope id="org.eclipse.cdt.core.g++"/> </provider> diff --git a/PlaygroundCpp/Sources/Playground.cpp b/PlaygroundCpp/Sources/Playground.cpp index dbb916c..d3330a1 100644 --- a/PlaygroundCpp/Sources/Playground.cpp +++ b/PlaygroundCpp/Sources/Playground.cpp @@ -1,97 +1,171 @@ -#include <algorithm> #include <iostream> -#include <climits> #include <vector> +#include <cmath> +#include <iomanip> +#include <algorithm> +#include <cfloat> //#include <gtest/gtest.h> using std::vector; +using std::min; -struct Segment { - int start, end; - bool operator==(const Segment &s1) { - return (start == s1.start && end == s1.end); +struct Point { + int x, y; + bool operator==(const Point &p1) { + return (x == p1.x && y == p1.y); } }; -bool sortSeg(Segment i, Segment j) { - if (i.start == j.start) { - return i.end < j.end; +bool sortPointXDimension(Point i, Point j) { + if (i.x == j.x) { + return i.y < j.y; } - return i.start < j.start; + return i.x < j.x; } -vector<int> fast_count_segments(vector<int> starts, vector<int> ends, - vector<int> points) { - // Implement algo described here, really clever: - // https://www.coursera.org/learn/algorithmic-toolbox/discussions/all/threads/QJ1jK9wNEeWdPBL2iFTrAw/replies/Ihiw4txhEeWK5g7mfcS2Xw/comments/oyAMaeIiEeWyqwpvChh66Q - // l->1, p->2, r->3 for Segment.end property - vector<Segment> s(starts.size() + ends.size() + points.size()); - vector<Segment> p(points.size()); - Segment tempSeg; - for (int i = 0; i < p.size(); i++) { - tempSeg = {points[i], i}; - p[i] = tempSeg; - tempSeg = {points[i], 2}; - s[2 * starts.size() + i] = tempSeg; + +bool sortPointYDimension(Point i, Point j) { + if (i.y == j.y) { + return i.x < j.x; } - for (int i = 0; i < starts.size(); i++) { - tempSeg = {starts[i], 1}; - s[i] = tempSeg; - tempSeg = {ends[i], 3}; - s[i + starts.size()] = tempSeg; + return i.y < j.y; +} + +float distance(Point p1, Point p2) { + return pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2); +} + +float baseCaseMinDistance(vector<Point> &ptsVector, int low, int high) { + if (high - low == 1) + return distance(ptsVector[low], ptsVector[high]); + if (high - low == 2) { + float f1 = distance(ptsVector[low], ptsVector[low + 1]); + float f2 = distance(ptsVector[low], ptsVector[high]); + float f3 = distance(ptsVector[high], ptsVector[low + 1]); + return min(f1, min(f2, f3)); } - std::sort(s.begin(), s.end(), sortSeg); - std::sort(p.begin(), p.end(), sortSeg); - vector<int> results(points.size()); - int count = 0; - int j = 0; - for (int i = 0; i < s.size(); i++) { - if (s[i].end == 1) { - count = count + 1; - } - if (s[i].end == 2) { - results[j] = count; - j = j + 1; - } - if (s[i].end == 3) { - count = count - 1; + float f1 = distance(ptsVector[low], ptsVector[low + 1]); + float f2 = distance(ptsVector[low], ptsVector[low + 2]); + float f3 = distance(ptsVector[low], ptsVector[high]); + float f4 = distance(ptsVector[low + 1], ptsVector[low + 2]); + float f5 = distance(ptsVector[low + 1], ptsVector[high]); + float f6 = distance(ptsVector[low + 2], ptsVector[high]); + return min(f1, min(f2, min(f3, min(f4, min(f5, f6))))); +} + +float dPrimeDistance(vector<Point> &shadedPoints) { + float minDistance = FLT_MAX; + float tempDistance; + for (int i = 0; i < shadedPoints.size(); i++) { + for (int j = 1; j <= 5; j++) { + if (i + j < shadedPoints.size()) { + tempDistance = distance(shadedPoints[i], shadedPoints[i + j]); + minDistance = min(tempDistance, minDistance); + } } } - vector<int> finalResults(points.size()); - for (int i = 0; i < finalResults.size(); i++) { - finalResults[p[i].end] = results[i]; + return minDistance; +} + +float minimalDistance(vector<Point> &ptsVector, int low, int high) { + if (high - low <= 3) { + return baseCaseMinDistance(ptsVector, low, high); + } + int mid = low + (high - low) / 2; + long midX = ptsVector[mid].x; + float f1 = minimalDistance(ptsVector, low, mid - 1); + float f2 = minimalDistance(ptsVector, mid, high); + float f = min(f1, f2); + vector<Point> shadedPoints; + for (int i = low; i <= high; i++) { + if (abs(ptsVector[i].x - midX) <= f) + shadedPoints.push_back(ptsVector[i]); } - return finalResults; + + std::sort(shadedPoints.begin(), shadedPoints.end(), sortPointYDimension); + + float fPrime = dPrimeDistance(shadedPoints); + + return min(f, fPrime); } +float minimalDistance(vector<int> &x, vector<int> &y) { + vector<Point> ptsVector(x.size()); + Point tempP; + + for (int i = 0; i < x.size(); i++) { + tempP = {x[i],y[i]}; + ptsVector[i] = tempP; + } -//TEST(SortSegment, Sort1) { -// vector<int> starts = { 0, 7 }; -// vector<int> ends = { 5, 10 }; -// vector<int> points = { 1, 6, 11 }; -// vector<int> results = { 1, 0, 0 }; + std::sort(ptsVector.begin(), ptsVector.end(), sortPointXDimension); + return sqrt(minimalDistance(ptsVector, 0, ptsVector.size() - 1)); +} +//TEST(SortPoint, Sort1) { +// vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 }; +// vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 }; +// vector<Point> p; +// Point tempP; +// +// for (int i = 0; i < x.size(); ++i) { +// tempP = {x[i],y[i]}; +// p.push_back(tempP); +// }; +// +// std::sort(p.begin(), p.end(), sortPointXDimension); +// +// ASSERT_EQ(p[0].x, -4); +// ASSERT_EQ(p[0].y, 0); +// +// std::sort(p.begin(), p.end(), sortPointYDimension); +// ASSERT_EQ(p[0].y, -4); +// ASSERT_EQ(p[0].x, -3); +// ASSERT_EQ(p[10].y, 4); +// ASSERT_EQ(p[10].x, 4); +//} +// +//TEST(PointDistance, Test1) { +// vector<int> x = { 0, 0 }; +// vector<int> y = { 3, 4 }; +// +// float f = minimalDistance(x, y); +// ASSERT_FLOAT_EQ(f, 5); +//} // -// vector<int> cnt = fast_count_segments(starts, ends, points); +//TEST(ClosestDistance, Test1) { +// vector<int> x = { 0, 3 }; +// vector<int> y = { 0, 4 }; +// float result = 5.0; +// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); +//} // -// ASSERT_EQ(cnt[0], 1); -// ASSERT_EQ(cnt[1], 0); -// ASSERT_EQ(cnt[2], 0); -// ASSERT_EQ(cnt.size(), 3); +//TEST(ClosestDistance, Test2) { +// vector<int> x = { 0, 3, 5 }; +// vector<int> y = { 0, 4, 6 }; +// float result = 2.828427; +// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); +//} +// +//TEST(ClosestDistance, Test3) { +// vector<int> x = { 7, 1, 4, 7 }; +// vector<int> y = { 7, 100, 8, 7 }; +// float result = 0.0; +// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); +//} +// +//TEST(ClosestDistance, Test4) { +// vector<int> x = { 4, -2, -3, -1, 2, -4, 1, -1, 3, -4, -2 }; +// vector<int> y = { 4, -2, -4, 3, 3, 0, 1, -1, -1, 2, 4 }; +// float result = 1.4142135; +// ASSERT_FLOAT_EQ(result, minimalDistance(x, y)); //} int main() { - int n, m; - std::cin >> n >> m; - vector<int> starts(n), ends(n); - for (size_t i = 0; i < starts.size(); i++) { - std::cin >> starts[i] >> ends[i]; - } - vector<int> points(m); - for (size_t i = 0; i < points.size(); i++) { - std::cin >> points[i]; - } - //use fast_count_segments - vector<int> cnt = fast_count_segments(starts, ends, points); - for (size_t i = 0; i < cnt.size(); i++) { - std::cout << cnt[i] << ' '; + size_t n; + std::cin >> n; + vector<int> x(n); + vector<int> y(n); + for (size_t i = 0; i < n; i++) { + std::cin >> x[i] >> y[i]; } + std::cout << std::fixed; + std::cout << std::setprecision(9) << minimalDistance(x, y) << "\n"; } - |