Guest User

Untitled

a guest
Nov 14th, 2015
376
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <stdlib.h>
  5. using namespace std;
  6. struct v2
  7. {int x;
  8. int y;
  9. };
  10.  
  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.  
  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. v2 c1,c2,c3,c4;
  54. c1.x = 0;
  55. c1.y=0;
  56. c2.x = 0;
  57. c2.y = 500;
  58. c3.x = 100000;
  59. c3.y = 0;
  60. c4.x = 100000;
  61. c4.y = 500;
  62. vs.push_back(c1);
  63. // vs.push_back(c2);
  64. vs.push_back(c3);
  65. // vs.push_back(c4);
  66. // vs2.push_back(c1);
  67. vs2.push_back(c2);
  68. // vs2.push_back(c3);
  69. vs2.push_back(c4);
  70.  
  71. sort(vs.begin(),vs.end(), sort1);
  72. sort(vs2.begin(),vs2.end(), sort2);
  73.  
  74. long long max = 0;
  75.  
  76. for(int i =0;i<vs.size()-1;i++)
  77. {
  78. // cout << "C: " << vs[i].x<<" " << vs[i].y<<"\n";
  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.  
  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. for(int i =1;i<vs.size() -1;i++)
  97. {
  98.  
  99. int j = i-1;
  100. while(vs[j].y > vs[i].y)
  101. j--;
  102. int k = i +1;
  103. while(vs[k].y >= vs[i].y)
  104. k++;
  105. long long area = vs[i].y*(vs[k].x - vs[j].x);
  106. //cout << " A: " << vs[j].x << " "<< vs[k].x << " "<<vs[i].y<<"\n";
  107. if(area > max)
  108. max=area;
  109. }
  110.  
  111. cout << max;
  112. }
RAW Paste Data