Advertisement
minimario

Watering the Fields

Jul 7th, 2015
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include <cstdio>
  2. #include <bitset>
  3. #include <iomanip>
  4. #include <cmath>
  5. #include <queue>
  6. #include <algorithm>
  7. #define pb push_back
  8. #define mp make_pair
  9. #include <iostream>
  10. #include <queue>
  11. #include <map>
  12. #include <vector>
  13. #include <string>
  14. #define ll long long
  15. using namespace std;
  16.  
  17. bool taken[2005][2005];
  18.  
  19. vector<pair<int,int> > g;
  20. priority_queue< vector<int>, vector<vector<int> >, greater<vector<int> > > pq;
  21. int x, c;
  22.  
  23. void process(int a, int b) {
  24.     taken[a][b] = true;
  25.     for (int i=0; i < g.size(); i++) {
  26.         pair<int, int> pr = g[i];
  27.         int dist = (a - pr.first)*(a-pr.first) + (b-pr.second)*(b-pr.second);
  28.         if (!taken[pr.first][pr.second] && dist >= c) {
  29.             vector<int> v;
  30.             v.pb(dist);
  31.             v.pb(pr.first);
  32.             v.pb(pr.second);
  33.             pq.push(v);
  34.  
  35.         }
  36.     }
  37. }
  38.  
  39. int a, b;
  40. int main() {
  41.     freopen("irrigation.in", "r", stdin);
  42.     freopen("irrigation.out", "w", stdout);
  43.     cin >> x >> c;
  44.     for (int i=0; i < x; i++) {
  45.         cin >> a >> b;
  46.         g.pb(mp(a,b));
  47.     }
  48.  
  49.     int dist = 0;
  50.     process(a, b);
  51.     while (!pq.empty()) {
  52.         vector<int> pr = pq.top();
  53.         pq.pop();
  54.         int x1 = pr[1];
  55.         int y1 = pr[2];
  56.         int c = pr[0];
  57.         if (!taken[x1][y1]) { dist += c; process(x1, y1);}
  58.     }
  59.  
  60.     cout << dist << endl;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement