SHARE
TWEET

sonar

a guest Jul 7th, 2010 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <list>
  4.  
  5. #define not_yet_set -1;
  6.  
  7. using namespace std;
  8.  
  9. typedef long int lint;
  10. typedef unsigned long long int ullint;
  11.  
  12. class target {
  13. public:
  14.     lint x, y;
  15. };
  16.  
  17. // overloading this operator will help us on list sorting.
  18. bool operator<(target a, target b)
  19. {
  20.     return (a.x == b.x) ? (a.x < b.x) : (a.y < b.y);
  21. }
  22.  
  23. int main()
  24. {
  25.     lint N, w;
  26.     ullint M1, M2;
  27.  
  28.     ifstream fin ("sonar.in");
  29.     ofstream fout("sonar.out");
  30.  
  31.     target point;
  32.     list<target> targets;
  33.  
  34.     // Beginning of Input
  35.     fin >> N >> M1 >> M2;
  36.     for(ullint i=0; i<M1; i++)
  37.     {
  38.         fin >> point.x >> w; // we are given the pos in x axis.
  39.         point.y = N - w + 1; // process the signal to get the pos in y axis.
  40.         targets.push_back(point);
  41.     }
  42.  
  43.     for(ullint i=0; i<M2; i++)
  44.     {
  45.         fin >> point.y >> w;
  46.         point.x = N - w + 1;
  47.         targets.push_back(point);
  48.     }
  49.     // End of input.
  50.  
  51.     targets.sort();
  52.  
  53.     target last;
  54.     last.x = last.y = not_yet_set;
  55.  
  56.     list<target>::iterator it;
  57.     for(it = targets.begin(); it != targets.end(); it++)
  58.     {
  59.         //since the list is sorted, same instances of a point are near.
  60.         if(it->x == last.x && it->y == last.y)
  61.         {
  62.             //if we find a double appearance, we must remove
  63.             // the other  instances of that point from our list.
  64.             it = targets.erase(it);
  65.             it--;
  66.             continue;
  67.         }
  68.  
  69.         last.x = it->x;
  70.         last.y = it->y;
  71.     }
  72.  
  73.     //Output the final solution.
  74.     fout << (int) targets.size() << "\n";
  75.     for(it=targets.begin(); it != targets.end(); it++)
  76.         fout << it->x << " " << it->y << "\n";
  77.  
  78.     //And pray for the testcases:
  79.     // *pray* *pray*...
  80.  
  81.     fin.close();
  82.     fout.close();
  83.     return 0;
  84. }
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