Advertisement
Guest User

Untitled

a guest
Dec 21st, 2015
404
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.56 KB | None | 0 0
  1. #include<fstream>
  2. #include<iostream>
  3. #include<vector>
  4. #include<set>
  5.  
  6. #define x first
  7. #define y second
  8. #define mp make_pair
  9. #define pb push_back
  10.  
  11. using namespace std;
  12. typedef pair<int, int> pii;
  13.  
  14. int n,a,b;
  15. vector<pii> T, st, st1, st2, rest;
  16.  
  17. set<pii> QQ;
  18. set<pii>::iterator t;
  19.  
  20. int v_prod(pii a, pii b, pii c){
  21.  
  22. int abx = b.x-a.x;
  23. int aby = b.y-a.y;
  24. int bcx = c.x-b.x;
  25. int bcy = c.y-b.y;
  26.  
  27. return abx*bcy - bcx*aby;
  28.  
  29. }
  30.  
  31. int main(){
  32. //ifstream cin("input.txt");ofstream cout("output.txt");
  33.  
  34. cin>>n;
  35.  
  36.  
  37.  
  38.  
  39.  
  40. for(int i = 0; i < n; i++) {
  41. cin>>a>>b;
  42. QQ.insert(mp(a,b));
  43. }
  44.  
  45. for (t = QQ.begin(); t!=QQ.end(); t++) T.pb((*t));
  46.  
  47.  
  48.  
  49.  
  50.  
  51. st.resize(0);
  52. st.pb(T[0]);
  53.  
  54. for(int i = 1; i < T.size(); i++){
  55.  
  56. bool flag = 1;
  57.  
  58. while((int)st.size() > 1 && flag == 1){
  59. flag = 0;
  60. if(v_prod(st[(int)st.size()-2], st[(int) st.size()-1], T[i]) < 0)
  61. {
  62. st.pop_back();
  63. flag = 1;
  64. }
  65. }
  66.  
  67. st.pb(T[i]);
  68. }
  69.  
  70. st1 = st;
  71.  
  72. st.resize(0);
  73. st.pb(T[0]);
  74.  
  75. for(int i = 1; i < T.size(); i++){
  76.  
  77. bool flag = 1;
  78.  
  79. while((int)st.size() > 1 && flag == 1){
  80. flag = 0;
  81. if(v_prod(st[(int)st.size()-2], st[(int) st.size()-1], T[i]) > 0)
  82. {
  83. st.pop_back();
  84. flag = 1;
  85. }
  86. }
  87.  
  88. st.pb(T[i]);
  89. }
  90.  
  91. st2 = st;
  92.  
  93.  
  94.  
  95.  
  96. rest = st1;
  97.  
  98. for(int i = st2.size()-2; i >=1; i--) rest.pb(st2[i]);
  99.  
  100. for(int i = 0; i < rest.size(); i++) cout<<rest[i].x<<' '<<rest[i].y<<endl;
  101.  
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement