Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <array>
- #include <random>
- #include <cmath>
- typedef std::array<double, 2> vector;
- typedef std::array<vector, 6> point_list;
- const auto pi = 4*std::atan(1);
- double random_uniform(double min, double max)
- {
- static std::default_random_engine generator;
- static std::uniform_real_distribution<double> unif_dist; // min = 0, max = 1
- return min + (max - min)*unif_dist(generator);
- }
- double distance(const vector& a, const vector& b)
- {
- return std::sqrt(std::pow(a[0] - b[0], 2) + std::pow(a[1] - b[1], 2));
- }
- bool inside_semicircle(const vector& p)
- {
- return p[1] >= 0 && (distance(p, vector()) <= 1);
- }
- void jostle_points(point_list& pl, double jostle_distance)
- {
- for(auto& p : pl)
- {
- while(true)
- {
- auto distance = random_uniform(0, jostle_distance);
- auto angle = random_uniform(0, 2*pi);
- auto dx = distance*std::cos(angle);
- auto dy = distance*std::sin(angle);
- auto np = p;
- np[0] += dx;
- np[1] += dy;
- if(inside_semicircle(np))
- {
- p = np;
- break;
- }
- }
- }
- }
- void write_list(const point_list& pl, std::ostream& os)
- {
- for(const auto& p : pl)
- {
- for(auto e : p)
- {
- os << e << ' ';
- }
- os << '\n';
- }
- os << "=====================================================" << std::endl;
- }
- std::ofstream ofs("result.txt");
- void write_list(const point_list& pl)
- {
- write_list(pl, std::cout);
- write_list(pl, ofs);
- }
- double minimum_distance(const point_list& pl, const vector& p)
- {
- auto min_dist = 1e6;
- for(const auto& pi : pl)
- {
- auto dis = distance(pi, p);
- if(dis < min_dist)
- {
- min_dist = dis;
- }
- }
- return min_dist;
- }
- double maximum_minimum_distance(const point_list& pl)
- {
- auto max_min_distance = 0.0;
- auto ds = 0.001;
- for(auto x = -1.0; x <= 1.0; x += ds)
- {
- for(auto y = -1.0; y <= 1.0; y += ds)
- {
- vector point = {{x, y}};
- if( ! inside_semicircle(point))
- {
- continue;
- }
- auto min_distance = minimum_distance(pl, point);
- if(min_distance > max_min_distance)
- {
- max_min_distance = min_distance;
- }
- }
- }
- return max_min_distance;
- }
- int main()
- {
- point_list pl;
- for(auto& p : pl)
- {
- p = {{0.0, 0.5}};
- }
- auto min_max_min_dis = 1e6;
- auto jostle_distance = 1.0;
- auto fail_count = 0;
- auto fail_threshold = 1000;
- auto success = false;
- write_list(pl);
- while(true)
- {
- auto new_pl = pl;
- jostle_points(new_pl, jostle_distance);
- double max_min_dis = maximum_minimum_distance(new_pl);
- if(max_min_dis < min_max_min_dis)
- {
- pl = new_pl;
- min_max_min_dis = max_min_dis;
- fail_count = 0;
- success = true;
- std::cout << "Maximum minimum distance = " << max_min_dis << std::endl;
- ofs << "Maximum minimum distance = " << max_min_dis << std::endl;
- write_list(pl);
- }
- else
- {
- std::cout << "Fail count (" << jostle_distance << ") = " << ++fail_count << '/' << fail_threshold << '\r';
- if(fail_count >= fail_threshold)
- {
- if(success)
- {
- jostle_distance *= 0.5;
- }
- else
- {
- jostle_distance *= 2.0;
- }
- if(jostle_distance < 1e-3 || jostle_distance > 2.0)
- {
- break;
- }
- fail_count = 0;
- success = false;
- std::cout << "New jostle distance = " << jostle_distance << std::endl;
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement