• API
• FAQ
• Tools
• Archive
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.
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.

Top