Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- deque<pair<int,int> > GET_CONVEX_HULL(){
- vector<pair<int,int> > arr;
- for(auto [y,x]: Set){
- arr.push_back({x,y});
- }
- ll buffer, xstart, ystart;
- xstart = arr[0].first;
- ystart = arr[0].second;
- sort(arr.begin()+1, arr.end(), [xstart, ystart, &buffer](pair<int,int> a,pair<int,int> b) {
- buffer = VectMultiply(xstart, ystart, a.first, a.second, xstart, ystart, b.first, b.second);
- if(buffer==0) return (a.second-ystart)*(a.second-ystart) + (a.first-xstart)*(a.first-xstart) <
- (b.second-ystart)* (b.second-ystart) + (b.first - xstart) * (b.first - xstart);
- return buffer>0;
- });
- deque<pair<int,int> > ans;
- ll curx = arr[1].first, cury = arr[1].second;
- ll nextx,nexty;
- ll prex = arr[0].first, prey = arr[0].second;
- ans.push_front(arr[0]);
- ans.push_front(arr[1]);
- int index = 1;
- buffer = 0;
- do{
- tie(curx, cury) = ans.front();
- index++;
- tie(nextx,nexty) = arr[index%n];
- //if(index == n) return ans;
- buffer = VectMultiply(prex, prey, curx, cury, curx, cury, nextx, nexty);
- //cout<<"{ "<<prex<<" , "<<prey<<" } { "<<curx<<" , "<<cury<<" } { "<<nextx<<" , "<<nexty<<" } "<<buffer<<" buffer"<<endl;
- if(buffer <= 0) {
- ans.pop_front();
- while(ans.size()>1){
- tie(curx, cury) = ans.front();
- ans.pop_front();
- tie(prex, prey) = ans.front();
- buffer = VectMultiply(prex, prey, curx, cury, curx, cury, nextx, nexty);
- //cout<<"{ "<<prex<<" , "<<prey<<" } { "<<curx<<" , "<<cury<<" } { "<<nextx<<" , "<<nexty<<" } "<<buffer<<" buffer1"<<endl;
- if(buffer>0){
- ans.push_front({curx, cury});
- break;
- }
- }
- }
- prex = curx;
- prey = cury;
- curx = nextx;
- cury = nexty;
- ans.push_front({curx, cury});
- } while(index!=n);
- return ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement