Advertisement
Guest User

Untitled

a guest
Aug 15th, 2015
306
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.94 KB | None | 0 0
  1. #pragma warning (disable : 4996)
  2.  
  3. #include <stdlib.h>
  4. #include <iostream>
  5. #include <vector>
  6. #include <string>
  7. #include <assert.h>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <ios>
  11. #include <iostream>
  12. #include <fstream>
  13. #include <iomanip>
  14. #include <queue>
  15. #include <set>
  16. #include <functional>
  17. #include <cmath>
  18. #include <sstream>
  19. #include <map>
  20. #include <memory.h>
  21. #include <stdio.h>
  22. #include <cassert>
  23. #include <string.h>
  24. #include <unordered_map>
  25.  
  26. #define forn(i , n) for (int i = 0; i < n; ++i)
  27. #define down(i, n) for (int i = n - 1; i >= 0; --i)
  28.  
  29. using namespace std;
  30.  
  31. typedef unsigned long long int u64;
  32. typedef long long int i64;
  33. typedef vector<i64> vint;
  34. typedef vector<i64> vi64;
  35. typedef pair<int, int> pint;
  36. typedef pair<i64, i64> pi64;
  37.  
  38. #define FILE_NAME "file"
  39. struct Node
  40. {
  41.     vector<i64> nbr;
  42.     i64 x, y;
  43.     i64 used;
  44.     i64 best;
  45.     i64 what;
  46.     Node()
  47.     {
  48.         used = 0;
  49.         best = 1000000000000000LL;
  50.  
  51.     }
  52.  
  53. };
  54.  
  55. struct Comp
  56. {
  57.     i64 n;
  58.     i64 t;
  59.     i64 p;
  60.     bool operator<(const Comp & b) const
  61.     {
  62.         return p < b.p;
  63.     }
  64. };
  65.  
  66.  
  67. const i64 inf = 1000000000000LL;
  68.  
  69.  
  70.  
  71. void calc(vector<Comp> & s, vector<Comp> & t, i64 j, i64 b, i64 & bNumb, i64 & p)
  72. {
  73.     i64 i = 0;
  74.     p = 0;
  75.     bNumb = 0;
  76.     while (b > 0)
  77.     {
  78.         if (i < s.size())
  79.         {
  80.             if (j < t.size())
  81.             {
  82.                 if (s[i] < t[j])
  83.                 {
  84.                     p += s[i].p;
  85.                     ++i;
  86.                 }
  87.                 else
  88.                 {
  89.                     p += t[j].p;
  90.                     ++j;
  91.                 }
  92.             }
  93.             else
  94.             {
  95.                 p += s[i].p;
  96.                 ++i;
  97.             }
  98.         }
  99.         else if (j < t.size())
  100.         {
  101.             p += t[j].p;
  102.             ++j;
  103.         }
  104.         else
  105.         {
  106.             break;
  107.         }
  108.         bNumb++;
  109.         --b;
  110.     }
  111.  
  112.  
  113.  
  114. }
  115.  
  116. void calcPrint(vector<Comp> & s, vector<Comp> & t, i64 j, i64 b, i64 & bNumb, i64 & p, i64 from)
  117. {
  118.     i64 i = 0;
  119.     p = 0;
  120.     bNumb = 0;
  121.     i64 n = from;
  122.     while (b > 0)
  123.     {
  124.         if (i < s.size())
  125.         {
  126.             if (j < t.size())
  127.             {
  128.                 if (s[i] < t[j])
  129.                 {
  130.                     p += s[i].p;
  131.                     cout << s[i].n << " " << from << "\n";
  132.                     ++from;
  133.                     ++i;
  134.  
  135.                 }
  136.                 else
  137.                 {
  138.                     p += t[j].p;
  139.                     cout << t[j].n << " " << from << "\n";
  140.                     ++from;
  141.                     ++j;
  142.                 }
  143.             }
  144.             else
  145.             {
  146.                 p += s[i].p;
  147.                 cout << s[i].n << " " << from << "\n";
  148.                 ++from;
  149.                 ++i;
  150.             }
  151.         }
  152.         else if (j < t.size())
  153.         {
  154.             p += t[j].p;
  155.             cout << t[j].n << " " << from << "\n";
  156.             ++from;
  157.             ++j;
  158.         }
  159.         else
  160.         {
  161.             break;
  162.         }
  163.         bNumb++;
  164.         --b;
  165.     }
  166.  
  167.  
  168.  
  169. }
  170.  
  171. struct Scene
  172. {
  173.     double x;
  174.     double bestL, bestR;
  175.     i64 n;
  176.  
  177.     bool operator<(const Scene & b) const
  178.     {
  179.         return x < b.x;
  180.     }
  181. };
  182.  
  183. bool cmp(const Scene& a, const Scene & b)
  184. {
  185.     return a.n < b.n;
  186. }
  187.  
  188.  
  189. i64 R;
  190.  
  191. bool check(double x, double y)
  192. {
  193.     double d = fabs(x - y);
  194.     d *= d;
  195.     if (R*R < d + 1)
  196.     {
  197.         return false;
  198.     }
  199.     return true;
  200. }
  201.  
  202. int main()
  203. {
  204.     ios_base::sync_with_stdio(false);
  205.     cin.tie(NULL);
  206.     cout << fixed << setprecision(15);
  207. #ifdef FILE_INPUT
  208.     freopen(FILE_NAME ".in", "r", stdin);
  209.     freopen(FILE_NAME ".out", "w", stdout);
  210. #endif
  211.     i64 n = 0;
  212.     i64 m = 0;
  213.     cin >> m >> n;
  214.    
  215.     cin >> R;
  216.     vector<double> c(m);
  217.     vector<Scene> s(n);
  218.    
  219.     forn(i, m)
  220.     {
  221.         cin >> c[i];
  222.     }
  223.     forn(i, n)
  224.     {
  225.         cin >> s[i].x;
  226.         s[i].n = i;
  227.     }
  228.     sort(s.begin(), s.end());
  229.  
  230.     i64 l = 0, r = 0;
  231.     forn(i, n)
  232.     {
  233.         while (!check(s[i].x, c[l]))
  234.         {
  235.             ++l;
  236.         }
  237.         s[i].bestL = c[l];
  238.         r = max(l, r);
  239.         while (r + 1 < m && check(s[i].x, c[r + 1]))
  240.         {
  241.             ++r;
  242.         }
  243.         s[i].bestR = c[r];
  244.     }
  245.  
  246.  
  247.     sort(s.begin(), s.end(), cmp);
  248.     double currPos = c[0];
  249.     double ans = 0;
  250.  
  251.     forn(i, n)
  252.     {
  253.         if (currPos >= s[i].bestL && currPos <= s[i].bestR)
  254.         {
  255.             continue;
  256.         }
  257.         else
  258.         {
  259.             if (fabs(s[i].bestL - currPos) < fabs(s[i].bestR - currPos))
  260.             {
  261.                 ans += fabs(s[i].bestL - currPos);
  262.                 currPos = s[i].bestL;
  263.             }
  264.             else
  265.             {
  266.                 ans += fabs(s[i].bestR - currPos);
  267.                 currPos = s[i].bestR;
  268.             }
  269.  
  270.         }
  271.     }
  272.     cout << ans;
  273.     return 0;
  274. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement