Advertisement
Guest User

Untitled

a guest
Oct 21st, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.97 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. ifstream fin("infasuratoare.in");
  5. ofstream fout("infasuratoare.out");
  6. const int NMAX=120003;
  7. struct Punct
  8. {
  9. double x,y;
  10. };
  11. Punct a[NMAX];
  12. int n,st[NMAX],top;
  13. bool viz[NMAX];
  14. ///v[i]->1 <=> pct i se afla pe stiva
  15.  
  16.  
  17.  
  18. ///returneaza <0 daca punctul a[p] este in semiplanul -
  19. ///al dreptei det. de punctele (a[i],a[j])
  20.  
  21. /**
  22. <0 ->semiplanul -
  23. >0 ->semiplanul +
  24. =0 ->coliniaritate
  25. */
  26. inline double F(int i,int j,int p)
  27. {
  28. return a[p].x*(a[i].y-a[j].y)+
  29. a[p].y*(a[j].x-a[i].x)+
  30. a[i].x*a[j].y-a[j].x*a[i].y;
  31. }
  32. inline void READ()
  33. {
  34. fin>>n;
  35. for(int i=1; i<=n; i++)
  36. fin>>a[i].x>>a[i].y;
  37.  
  38. }
  39. ///sortez punctele dupa y,in caz de egalitate dupa x
  40. inline bool Sort(const Punct A,const Punct B)
  41. {
  42. if(A.y==B.y)
  43. return A.x<B.x;
  44. return A.y<B.y;
  45. }
  46.  
  47.  
  48. ///algoritmul lui HILL
  49. inline void HILL()
  50. {
  51. sort(a+1,a+n+1,Sort);
  52. ///ca rezolvare folosim o stiva(de preferabil de mana)
  53. ++top;
  54. st[top]=1;
  55. ++top;
  56. st[top]=2;
  57. viz[2]=true;
  58. for(int i=3; i<=n; i++)
  59. {
  60. /**
  61. incercam sa punem pct i pe stiva
  62. scoatem punctele care se afla in semiplanul -,fata de pct i
  63. */
  64. while(top>1 && F(st[top-1],st[top],i)<0)
  65. {
  66. viz[st[top]]=false;
  67. top--;
  68. }
  69. ++top;
  70. st[top]=i;
  71. viz[i]=true;
  72. }
  73.  
  74. for(int i=n-1; i>=1; i--)
  75. if(!viz[i])
  76. {
  77. while(F(st[top-1],st[top],i)<0)
  78. {
  79. viz[st[top]]=false;
  80. top--;
  81. }
  82. ++top;
  83. st[top]=i;
  84. viz[i]=true;
  85. }
  86. }
  87. inline void Solve()
  88. {
  89. fout<<(top-1)<<"\n";
  90. for(int i=1;i<top;i++)
  91. fout<<fixed<<setprecision(12)<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
  92. }
  93. int main()
  94. {
  95. READ();
  96. HILL();
  97. Solve();
  98. fin.close();
  99. fout.close();
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement