Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct v2
- {int x;
- int y;
- };
- //sort by X values
- bool sort1(v2 a, v2 b)
- {
- if(a.x==b.x)
- return a.y < b.y;
- return a.x<b.x;
- }
- //Sort by Y values
- bool sort2(v2 a, v2 b)
- {
- if(a.y==b.y)
- return a.x < b.x;
- return a.y<b.y;
- }
- /*int binarysearch(int * ar,int target,int n,int x)
- {
- if(n==1)
- return x;
- else if(ar[n/2] >= target)
- return binarysearch(ar, target, n/2 + 1, x);
- else if(ar[n/2] < target)
- return binarysearch(ar + )
- }
- */
- int main()
- {
- int n;
- cin >> n;
- vector<v2> vs;
- vector<v2> vs2;
- for(int i =0;i<n;i++)
- {
- v2 abc;
- cin >> abc.x;
- cin >> abc.y;
- vs.push_back(abc);
- vs2.push_back(abc);
- }
- //corners
- v2 c1,c2,c3,c4;
- c1.x = 0;
- c1.y=0;
- c2.x = 0;
- c2.y = 500;
- c3.x = 100000;
- c3.y = 0;
- c4.x = 100000;
- c4.y = 500;
- vs.push_back(c1);
- // vs.push_back(c2);
- vs.push_back(c3);
- // vs.push_back(c4);
- // vs2.push_back(c1);
- vs2.push_back(c2);
- // vs2.push_back(c3);
- vs2.push_back(c4);
- sort(vs.begin(),vs.end(), sort1);
- sort(vs2.begin(),vs2.end(), sort2);
- long long max = 0;
- //This is rectangles will always lie on the x axis
- for(int i =0;i<vs.size()-1;i++)
- {
- long long area = (vs[i+1].x - vs[i].x) * 500;
- if(area > max )
- max = area;
- // cout <<" A: "<<vs[i+1].x<<" "<<vs[i].x <<" "<< area << "\n";
- }
- //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
- for(int i =0;i<vs2.size()-1;i++)
- {
- long long area = (vs2[i+1].y - vs2[i].y) * 100000;
- if(area > max && vs2[i].y==0)
- max = area;
- if(vs2[i].y!=0)
- break;
- // cout <<" B: "<<vs2[i+1].y<<" "<<vs2[i].y <<" "<< area << "\n";
- }
- //the harder casesss
- vector<int> xps; // keep track of x points which may prevent us from going further
- xps.push_back(0);
- xps.push_back(100000);
- for(int i =0;i<vs2.size()-1;i++)
- {
- int beg = 0, end = xps.size()-1;
- int xl, xg = 0; // find adjacent points which limit the size of the rectangle
- int mid = 0;
- while(beg<=end) // binary search
- {
- mid = (beg+end) /2;
- if(xps[mid] > vs2[i].x && xps[mid-1] < vs2[i].x)
- {
- xg=xps[mid];
- xl = xps[mid-1];
- break;
- }
- else if(xps[mid] > vs2[i].x && xps[mid-1] > vs2[i].x)
- {
- end = mid-1;
- }
- else
- {
- beg = mid+1;
- }
- }
- long long area = ( vs2[i].y) * (xg-xl);
- //xps.insert(xps.begin() + mid, vs2[i].x);
- xps.push_back(vs2[i].x);
- sort(xps.begin(), xps.end()); //keep the array sorted for binary search to work
- if(area > max)
- max = area;
- }
- cout << max;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement