daily pastebin goal
29%
SHARE
TWEET

Untitled

a guest Mar 18th, 2019 45 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <math.h>
  5. #include <algorithm>
  6. #include <chrono>
  7. #define Size Point
  8.  
  9. using namespace std;
  10.  
  11. int N, M, R;
  12.  
  13. struct Point {
  14.     int x, y;
  15.     Point() {}
  16.     Point(int _x, int _y) {
  17.         x = _x;
  18.         y = _y;
  19.     }
  20.     friend bool operator <(const Point& l, const Point& r);
  21.     friend bool operator >(const Point& l, const Point& r);
  22.     friend bool operator ==(const Point& l, const Point& r);
  23. };
  24.  
  25. bool operator <(const Point& l, const Point& r) {
  26.     if (l.y == r.y)
  27.         return l.x < r.x;
  28.     return l.y < r.y;
  29. }
  30. bool operator >(const Point& l, const Point& r) {
  31.     if (l.y == r.y)
  32.         return l.x > r.x;
  33.     return l.y > r.y;
  34. }
  35. bool operator ==(const Point& l, const Point& r) {
  36.     return l.x == r.x && l.y == r.y;
  37. }
  38.  
  39. /* Проверка на вместимость в карту */
  40. bool check_olymp(Size s) {
  41.     if (s.x > ::M || s.y > ::N)
  42.         return false;
  43.     return true;
  44. }
  45.  
  46. /* Двойной массив относительных точек центров двух колец */
  47. vector<Point> build_map() {
  48.     vector<Point> map;
  49.     int count = 0;
  50.     for (int x = 1; x < 2 * R; ++x) {
  51.         for (int y = 1; y < 2 * R; ++y)
  52.             if (x * x + y * y < 4 * R * R) {
  53.                 map.push_back(Point(x, y));
  54.                 //cout << x << '-' << y << endl;
  55.                 ++count;
  56.             }
  57.     }
  58.     cout << count << endl << pow(count, 4) << endl;
  59.     return map;
  60. }
  61.  
  62. vector<Point> build_delete_map() {
  63.     vector<Point> map;
  64.     for (int x = 2 * R - 1; x > 1; --x)
  65.         for (int y = 2 * R - 1; y > 1; --y)
  66.             if (x * x + y * y >= 4 * R * R)
  67.                 map.push_back(Point(x, y));
  68.     return map;
  69. }
  70.  
  71. map<Size, int> build_full(map<Size, int> map_y, map<Size, int> map_x) {
  72.     map<Size, int> new_map;
  73.     for (map<Size, int>::iterator it = map_x.begin(); it != map_x.end(); ++it) {
  74.         for (map<Size, int>::iterator _it = map_y.begin(); _it != map_y.end(); ++_it) {
  75.             //cout << "x:" << it->first.x << "\ty:" << _it->first.y << endl;
  76.             new_map[Size(it->first.x, _it->first.y)] = it->second * _it->second;
  77.         }
  78.     }
  79.     return new_map;
  80. }
  81. map<Size, int> build_osnovanie() {
  82.     map<Size, int> size_map;
  83.     vector<Point> _map;
  84.     for (int x = 1; x < 2 * R; ++x)
  85.         _map.push_back(Point(x, 1));
  86.     Point p1(0, 0);
  87.     for (vector<Point>::iterator i2 = _map.begin(); i2 != _map.end(); ++i2) {
  88.         Point p2(p1.x + (*i2).x, p1.y - (*i2).y);
  89.         for (vector<Point>::iterator i3 = _map.begin(); i3 != _map.end(); ++i3) {
  90.             Point p3(p2.x + (*i3).x, p2.y + (*i3).y);
  91.             for (vector<Point>::iterator i4 = _map.begin(); i4 != _map.end(); ++i4) {
  92.                 Point p4(p3.x + (*i4).x, p3.y - (*i4).y);
  93.                 for (vector<Point>::iterator i5 = _map.begin(); i5 != _map.end(); ++i5) {
  94.                     Point p5(p4.x + (*i5).x, p4.y + (*i5).y);
  95.                     Size size = Size(p5.x - p1.x, max(p1.y, max(p3.y, p5.y)) - min(p2.y, p4.y));
  96.                     std::map<Size, int>::iterator it = size_map.find(size);
  97.                     if (it != size_map.end()) it->second++;
  98.                     else size_map[size] = 1;
  99.                 }
  100.             }
  101.         }
  102.     }
  103.     _map.clear();
  104.     map <Size, int> __map;
  105.     for (int y = 1; y < 2 * R; ++y)
  106.         _map.push_back(Point(1, y));
  107.     for (vector<Point>::iterator i2 = _map.begin(); i2 != _map.end(); ++i2) {
  108.         Point p2(p1.x + (*i2).x, p1.y - (*i2).y);
  109.         for (vector<Point>::iterator i3 = _map.begin(); i3 != _map.end(); ++i3) {
  110.             Point p3(p2.x + (*i3).x, p2.y + (*i3).y);
  111.             for (vector<Point>::iterator i4 = _map.begin(); i4 != _map.end(); ++i4) {
  112.                 Point p4(p3.x + (*i4).x, p3.y - (*i4).y);
  113.                 for (vector<Point>::iterator i5 = _map.begin(); i5 != _map.end(); ++i5) {
  114.                     Point p5(p4.x + (*i5).x, p4.y + (*i5).y);
  115.                     Size size = Size(p5.x - p1.x, max(p1.y, max(p3.y, p5.y)) - min(p2.y, p4.y));
  116.                     std::map<Size, int>::iterator it = __map.find(size);
  117.                     if (it != __map.end()) it->second++;
  118.                     else __map[size] = 1;
  119.                 }
  120.             }
  121.         }
  122.     }
  123.  
  124.     return build_full(__map, size_map);
  125. }
  126. map<Size, int> build_size(vector<Point> map) {
  127.     std::map<Size, int> size_map;
  128.     Point p1(0, 0);
  129.     for (vector<Point>::iterator i2 = map.begin(); i2 != map.end(); ++i2) {
  130.         Point p2(p1.x + (*i2).x, p1.y - (*i2).y);
  131.         for (vector<Point>::iterator i3 = map.begin(); i3 != map.end(); ++i3) {
  132.             Point p3(p2.x + (*i3).x, p2.y + (*i3).y);
  133.             for (vector<Point>::iterator i4 = map.begin(); i4 != map.end(); ++i4) {
  134.                 Point p4(p3.x + (*i4).x, p3.y - (*i4).y);
  135.                 for (vector<Point>::iterator i5 = map.begin(); i5 != map.end(); ++i5) {
  136.                     Point p5(p4.x + (*i5).x, p4.y + (*i5).y);
  137.                     Size size = Size(p5.x - p1.x, max(p1.y, max(p3.y, p5.y)) - min(p2.y, p4.y));
  138.                     std::map<Size, int>::iterator it = size_map.find(size);
  139.                     if (it != size_map.end()) it->second++;
  140.                     else size_map[size] = 1;
  141.                 }
  142.             }
  143.         }
  144.     }
  145.     return size_map;
  146. }
  147. //vector<tuple<Size, int>> build_size(vector<vector<Point>> map) {
  148. //  if (R == 1) {
  149. //      vector<tuple<Size, int>> size;
  150. //      size.push_back(tuple<Size, int>(Size(6, 3), 1));
  151. //      return size;
  152. //  }
  153. //
  154. //  int len_x = map.size();
  155. //
  156. //  for (int i = 0; i < len_x - 1; ++i) {
  157. //      int len_y = map[i].size();
  158. //      for (int i2 = i; i2 < len_x; ++i2) {
  159. //          int len_y2 = map[i2].size();
  160. //
  161. //      }
  162. //  }
  163. //  return;
  164. //}
  165.  
  166. map<Size, int> delete_this(map<Size, int> size_map, vector<Point> delete_map) {
  167.     Point p1(0, 0);
  168.     for (vector<Point>::iterator i2 = delete_map.begin(); i2 != delete_map.end(); ++i2) {
  169.         Point p2(p1.x + (*i2).x, p1.y - (*i2).y);
  170.         for (vector<Point>::iterator i3 = delete_map.begin(); i3 != delete_map.end(); ++i3) {
  171.             Point p3(p2.x + (*i3).x, p2.y + (*i3).y);
  172.             for (vector<Point>::iterator i4 = delete_map.begin(); i4 != delete_map.end(); ++i4) {
  173.                 Point p4(p3.x + (*i4).x, p3.y - (*i4).y);
  174.                 for (vector<Point>::iterator i5 = delete_map.begin(); i5 != delete_map.end(); ++i5) {
  175.                     Point p5(p4.x + (*i5).x, p4.y + (*i5).y);
  176.                     Size size = Size(p5.x - p1.x, max(p1.y, max(p3.y, p5.y)) - min(p2.y, p4.y));
  177.                     size_map.find(size)->second--;
  178.                 }
  179.             }
  180.         }
  181.     }
  182.     return size_map;
  183. }
  184.  
  185. int main() {
  186.     int n, m, r;
  187.     cin >> m >> n >> r;
  188.     ::M = m;
  189.     ::N = n;
  190.     ::R = r;
  191.  
  192.     //vector<Point> map = build_map();
  193.     //std::map<Size, int> size_map = build_size(map);
  194.     //for (std::map<Size, int>::iterator it = size_map.begin(); it != size_map.end(); ++it) {
  195.     //  cout << it->first.x << '-' << it->first.y << ":\t" << it->second << endl;
  196.     //}
  197.     chrono::high_resolution_clock::time_point t1 = chrono::high_resolution_clock::now();
  198.     std::map<Size, int> size_map = build_osnovanie();
  199.     chrono::high_resolution_clock::time_point t2 = chrono::high_resolution_clock::now();
  200.     vector<Point> _size = build_delete_map();
  201.     chrono::high_resolution_clock::time_point t3 = chrono::high_resolution_clock::now();
  202.     map<Size, int> correct = delete_this(size_map, _size);
  203.     chrono::high_resolution_clock::time_point t4 = chrono::high_resolution_clock::now();
  204.     for (std::map<Size, int>::iterator it = size_map.begin(); it != size_map.end(); ++it) {
  205.         cout << it->first.x << '-' << it->first.y << ":\t" << it->second << endl;
  206.     }
  207.     cout << "----------------------" << endl;
  208.     for (std::map<Size, int>::iterator it = correct.begin(); it != correct.end(); ++it) {
  209.         cout << it->first.x << '-' << it->first.y << ":\t" << it->second << endl;
  210.     }
  211.     chrono::duration<double> time_span1 = chrono::high_resolution_clock::duration(t2 - t1);
  212.     chrono::duration<double> time_span2 = chrono::high_resolution_clock::duration(t3 - t2);
  213.     chrono::duration<double> time_span3 = chrono::high_resolution_clock::duration(t4 - t3);
  214.     cout << time_span1.count() << '\t' << time_span2.count() << '\t' << time_span3.count() << endl;
  215.  
  216.     system("pause");
  217.     return 0;
  218. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top