Guest User

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