Advertisement
999ms

GOVNO

Apr 22nd, 2020
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  1. deque<pair<int,int> > GET_CONVEX_HULL(){
  2. vector<pair<int,int> > arr;
  3. for(auto [y,x]: Set){
  4. arr.push_back({x,y});
  5. }
  6. ll buffer, xstart, ystart;
  7. xstart = arr[0].first;
  8. ystart = arr[0].second;
  9. sort(arr.begin()+1, arr.end(), [xstart, ystart, &buffer](pair<int,int> a,pair<int,int> b) {
  10. buffer = VectMultiply(xstart, ystart, a.first, a.second, xstart, ystart, b.first, b.second);
  11. if(buffer==0) return (a.second-ystart)*(a.second-ystart) + (a.first-xstart)*(a.first-xstart) <
  12. (b.second-ystart)* (b.second-ystart) + (b.first - xstart) * (b.first - xstart);
  13. return buffer>0;
  14. });
  15. deque<pair<int,int> > ans;
  16. ll curx = arr[1].first, cury = arr[1].second;
  17. ll nextx,nexty;
  18. ll prex = arr[0].first, prey = arr[0].second;
  19. ans.push_front(arr[0]);
  20. ans.push_front(arr[1]);
  21. int index = 1;
  22. buffer = 0;
  23. do{
  24. tie(curx, cury) = ans.front();
  25. index++;
  26. tie(nextx,nexty) = arr[index%n];
  27. //if(index == n) return ans;
  28. buffer = VectMultiply(prex, prey, curx, cury, curx, cury, nextx, nexty);
  29. //cout<<"{ "<<prex<<" , "<<prey<<" } { "<<curx<<" , "<<cury<<" } { "<<nextx<<" , "<<nexty<<" } "<<buffer<<" buffer"<<endl;
  30. if(buffer <= 0) {
  31. ans.pop_front();
  32. while(ans.size()>1){
  33. tie(curx, cury) = ans.front();
  34. ans.pop_front();
  35. tie(prex, prey) = ans.front();
  36. buffer = VectMultiply(prex, prey, curx, cury, curx, cury, nextx, nexty);
  37. //cout<<"{ "<<prex<<" , "<<prey<<" } { "<<curx<<" , "<<cury<<" } { "<<nextx<<" , "<<nexty<<" } "<<buffer<<" buffer1"<<endl;
  38. if(buffer>0){
  39. ans.push_front({curx, cury});
  40. break;
  41. }
  42. }
  43. }
  44. prex = curx;
  45. prey = cury;
  46. curx = nextx;
  47. cury = nexty;
  48. ans.push_front({curx, cury});
  49. } while(index!=n);
  50. return ans;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement