# Two rectangles

Feb 6th, 2015
55
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <algorithm>
2. #include <iostream>
3. #include <iterator>
4. #include <vector>
5. #include <cmath>
6.
7. typedef std::tuple<unsigned long long, unsigned long long> rectangle;
9.
10. rectangle best_permiter(const unsigned long long p) {
11.     unsigned long long best = 2*(p + 1);
13.     for(unsigned long long i = 2; i*i <= p; ++i) {
14.         if(p % i == 0 && 2*(p/i+i) < best) {
16.             best = 2 * (p/i + i);
17.         }
18.     }
20. }
21.
22. inline unsigned long long permiter(const rectangle& x) {
23.     return 2 * (std::get<0>(x) + std::get<1>(x));
24. }
25.
26. std::vector<rectangle> make_cache() {
27.     constexpr size_t cache_size = 1300U*1000U;
28.     std::vector<rectangle> cache(cache_size + 1);
29.     cache.emplace_back(0,0);
30.     for(size_t i = 1; i < cache.size(); ++i) {
31.         cache[i] = rectangle(1, i);
32.     }
33.     for(unsigned i = 2; i < cache_size; ++i) {
34.         for(size_t j = i; j < cache.size(); j += i) {
35.             if(permiter(cache[j]) > 2 * (i + j/i)) {
36.                 cache[j] = rectangle(i, j/i);
37.             }
38.         }
39.     }
40.     return cache;
41. }
42.
43. answer solve(const unsigned long long begin, const unsigned long long end,
44.              const unsigned long long p) {
45.     if(p == 2) {
47.     }
48.     if(p < 100000) {
50.            unsigned long long square = sqrt(p), best = p*8;
51.            for(unsigned long long i = 1; i <= square; ++i) {
52.              for(unsigned long long j = 1; j * i < p; ++j) {
53.                auto temp = best_permiter(p - i*j);
54.                if(permiter(temp) + 2*(i+j) < best) {
55.                  result = answer(temp, rectangle(i, j));
56.                  best = permiter(temp) + 2 * (i + j);
57.                 }
58.               }
59.             }
60.            return result;
61.           }
62.     const static std::vector<rectangle> cache = make_cache();
64.     unsigned long long best = 0;
65.     bool first = true;
66.     unsigned long long square = sqrt(p);
67.     if(p < 100) {
68.         square = p-1;
69.     }
70.     for(unsigned long long i = begin; i <= end && i < square; ++i) {
71.         const auto first_side = square - i;
72.         const auto second_side = p / first_side;
73.         if(second_side == 0 || first_side * second_side == p) {
74.             continue;
75.         }
76.         auto first_rectangle = rectangle(first_side, second_side);
77.         auto rest = p - first_side * second_side;
78.         if(rest > cache.size()) {
79.             continue;
80.         }
81.         auto second_rectangle = rest < cache.size() ? cache[rest] :
82.                                         best_permiter(rest);
83.         auto sum_of_sides = std::get<0>(second_rectangle) +
84.                             std::get<1>(second_rectangle) +
85.                             std::get<0>(first_rectangle)  +
86.                             std::get<1>(first_rectangle);
87.         if(first == true || sum_of_sides < best) {
89.             best = sum_of_sides;
90.             first = false;
91.         }
92.     }
93.     return result;
94. }
95.
96. int main() {
97.     std::ios_base::sync_with_stdio(false);
98.     std::cin.tie(NULL);
99.     unsigned t;
100.     std::cin >> t;
101.     for(unsigned counter = 0; counter < t; ++counter) {
102.         unsigned long long p;
103.         std::cin >> p;
104.         unsigned long long begin = 0, end = 1000000;
105.         auto result = solve(begin, end, p);
106.         auto sum_of_permiter = permiter(std::get<0>(result)) +
107.                               permiter(std::get<1>(result));
108.         std::cout << sum_of_permiter << '\n';
109.         std::cout << std::get<0>(std::get<0>(result)) << ' '
110.                   << std::get<1>(std::get<0>(result)) << '\n'
111.                   << std::get<0>(std::get<1>(result)) << ' '
112.                   << std::get<1>(std::get<1>(result)) << '\n';
113.     }
114. }
RAW Paste Data