# Untitled

a guest
Nov 14th, 2015
250
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
5. struct v2
6. {int x;
7. int y;
8. };
9.
10. //sort by X values
11. bool sort1(v2 a, v2 b)
12. {
13. if(a.x==b.x)
14. return a.y < b.y;
15.
16. return a.x<b.x;
17. }
18. //Sort by Y values
19. bool sort2(v2 a, v2 b)
20. {
21. if(a.y==b.y)
22. return a.x < b.x;
23.
24. return a.y<b.y;
25. }
26.
27. /*int binarysearch(int * ar,int target,int n,int x)
28. {
29. if(n==1)
30. return x;
31. else if(ar[n/2] >= target)
32. return binarysearch(ar, target, n/2 + 1, x);
33. else if(ar[n/2] < target)
34. return binarysearch(ar + )
35. }
36. */
37. int main()
38. {
39. int n;
40. cin >> n;
41.
42. vector<v2> vs;
43. vector<v2> vs2;
44.
45. for(int i =0;i<n;i++)
46. {
47. v2 abc;
48. cin >> abc.x;
49. cin >> abc.y;
50. vs.push_back(abc);
51. vs2.push_back(abc);
52. }
53. //corners
54. v2 c1,c2,c3,c4;
55. c1.x = 0;
56. c1.y=0;
57. c2.x = 0;
58. c2.y = 500;
59. c3.x = 100000;
60. c3.y = 0;
61. c4.x = 100000;
62. c4.y = 500;
63. vs.push_back(c1);
64. // vs.push_back(c2);
65. vs.push_back(c3);
66. // vs.push_back(c4);
67. // vs2.push_back(c1);
68. vs2.push_back(c2);
69. // vs2.push_back(c3);
70. vs2.push_back(c4);
71.
72. sort(vs.begin(),vs.end(), sort1);
73. sort(vs2.begin(),vs2.end(), sort2);
74.
75. long long max = 0;
76. //This is rectangles will always lie on the x axis
77. for(int i =0;i<vs.size()-1;i++)
78. {
79. long long area = (vs[i+1].x - vs[i].x) * 500;
80. if(area > max )
81. max = area;
82. // cout <<" A: "<<vs[i+1].x<<" "<<vs[i].x <<" "<< area << "\n";
83. }
84. //The first in this case will also lie on the x axis, I was lazy and so I didn't remove the for loop :P
85. for(int i =0;i<vs2.size()-1;i++)
86. {
87. long long area = (vs2[i+1].y - vs2[i].y) * 100000;
88. if(area > max && vs2[i].y==0)
89. max = area;
90. if(vs2[i].y!=0)
91. break;
92. // cout <<" B: "<<vs2[i+1].y<<" "<<vs2[i].y <<" "<< area << "\n";
93.
94. }
95. //the harder casesss
96.
97. vector<int> xps; // keep track of x points which may prevent us from going further
98. xps.push_back(0);
99. xps.push_back(100000);
100. for(int i =0;i<vs2.size()-1;i++)
101. {
102. int beg = 0, end = xps.size()-1;
103. int xl, xg = 0; // find adjacent points which limit the size of the rectangle
104. int mid = 0;
105. while(beg<=end) // binary search
106. {
107. mid = (beg+end) /2;
108.
109. if(xps[mid] > vs2[i].x && xps[mid-1] < vs2[i].x)
110. {
111. xg=xps[mid];
112. xl = xps[mid-1];
113. break;
114. }
115. else if(xps[mid] > vs2[i].x && xps[mid-1] > vs2[i].x)
116. {
117. end = mid-1;
118. }
119. else
120. {
121. beg = mid+1;
122. }
123. }
124.
125. long long area = ( vs2[i].y) * (xg-xl);
126. //xps.insert(xps.begin() + mid, vs2[i].x);
127. xps.push_back(vs2[i].x);
128. sort(xps.begin(), xps.end()); //keep the array sorted for binary search to work
129. if(area > max)
130. max = area;
131. }
132. cout << max;
133. }
RAW Paste Data