Last active
January 13, 2017 14:51
-
-
Save carmelopellegrino/9460f1940b261d4076c69fedd1a1e254 to your computer and use it in GitHub Desktop.
farest-nearest
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <math.h> | |
| #include <vector> | |
| #include <fstream> | |
| #include <algorithm> | |
| #include <stdint.h> | |
| #include <cassert> | |
| struct point { | |
| double dist; | |
| int16_t x; | |
| int16_t y; | |
| }; | |
| template<typename T> | |
| T square(T const& value) | |
| { | |
| return value * value; | |
| } | |
| inline | |
| bool far(point const& first, point const& second) { | |
| return first.dist > second.dist; | |
| } | |
| inline | |
| bool near(point const& first, point const& second) { | |
| return !far(first, second); | |
| } | |
| int16_t swap(int16_t x) | |
| { | |
| unsigned char* p = (unsigned char*) &x; | |
| return p[1] + 256L * p[0]; | |
| } | |
| int main(int argc, char* argv[]) { | |
| if (argc != 2) { | |
| std::cerr << "Usage: " << argv[0] << " input-file-name\n"; | |
| return EXIT_FAILURE; | |
| } | |
| std::ifstream input(argv[1]); | |
| double const X1 = -200; | |
| double const Y1 = 300; | |
| double const X2 = 1000; | |
| double const Y2 = 25; | |
| int const NNEAR = 10; | |
| int const NFAR = 20; | |
| point nearest[NNEAR + 1]; | |
| point furthest[NFAR + 1]; | |
| for (int i = 0; i < NNEAR + 1; ++i) { | |
| nearest[i].dist = 1e308; | |
| } | |
| for (int i = 0; i < NFAR + 1; ++i) { | |
| furthest[i].dist = -1; | |
| } | |
| int const NPOINTS = 10000000; | |
| assert(NPOINTS > NFAR && NPOINTS > NNEAR); | |
| std::vector<std::pair<int16_t, int16_t>> data(NPOINTS); | |
| input.read((char*) &data.front(), 4 * data.size()); | |
| std::cout << "first points:\n"; | |
| for (int i = 0; i < 3; ++i) { | |
| std::cout << swap(data[i].first) << ' ' << swap(data[i].second) << '\n'; | |
| } | |
| for (int i = 0; i < data.size(); ++i) { | |
| int16_t const x = swap(data[i].first); | |
| int16_t const y = swap(data[i].second); | |
| double const distance21 = square(x - X1) + square(y - Y1); | |
| double const distance22 = square(x - X2) + square(y - Y2); | |
| if (distance21 < nearest[NNEAR - 1].dist) { | |
| nearest[NNEAR].x = x; | |
| nearest[NNEAR].y = y; | |
| nearest[NNEAR].dist = distance21; | |
| std::sort(nearest, nearest + NNEAR + 1, near); | |
| } | |
| if (distance22 > furthest[NFAR - 1].dist) { | |
| furthest[NFAR].x = x; | |
| furthest[NFAR].y = y; | |
| furthest[NFAR].dist = distance22; | |
| std::sort(furthest, furthest + NFAR + 1, far); | |
| } | |
| } | |
| std::cout << "Nearest points to (" << X1 << ", " << Y1 << "):\n"; | |
| for (int i = 0; i < NNEAR; ++i) { | |
| std::cout | |
| << nearest[i].x << ", " | |
| << nearest[i].y << " dist: " << sqrt(nearest[i].dist) << '\n'; | |
| } | |
| std::cout << "Furthest points to (" << X2 << ", " << Y2 << "):\n"; | |
| for (int i = 0; i < NFAR; ++i) { | |
| std::cout | |
| << furthest[i].x << ", " | |
| << furthest[i].y << " dist: " << sqrt(furthest[i].dist) << '\n'; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment