Rkhamim

Untitled

Mar 5th, 2021
142
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int flag;
  4. struct pt {
  5. int x,y,z;
  6. };
  7. bool cmp(pt a, pt b) {
  8. return a.x < b.x || (a.x == b.x && a.y < b.y);
  9. }
  10. int area(pt a, pt b, pt c) {
  11. return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
  12. }
  13. vector<int> convex_hull(vector<pt>& a) {
  14. sort(a.begin(), a.end(), &cmp);
  15. pt p1 = a[0], p2 = a.back();
  16. vector<int> up, down,p;
  17. up.push_back(p1.z);
  18. for (int i = 1; i < (int)a.size()-1; i++) {
  19. if (area(p1, a[i], p2)<0) {
  20. flag=2;
  21. }
  22. else if (area(p1, a[i], p2)>0) {
  23. down.push_back(a[i].z);
  24. flag=1;
  25. }
  26. }
  27. for (int i = 1; i < (a.size()-1); i++) {
  28. if (area(p1, a[i], p2)==0) {
  29. if(flag==2)down.push_back(a[i].z);
  30. else
  31. up.push_back(a[i].z);
  32. }
  33. else if (area(p1, a[i], p2)>0) {
  34. down.push_back(a[i].z);
  35. }
  36. else
  37. {
  38. up.push_back(a[i].z);
  39. }
  40. }
  41. down.push_back(p2.z);
  42. for (int i = 0; i < (int)a.size()-1; i++) {
  43. if(a[i].x==a[i+1].x&&a[i].y==a[i+1].y)flag=0;
  44. }
  45. a.clear();
  46. for (int i = down.size() -1; i >=0; i--)
  47. up.push_back(down[i]);
  48. return up;
  49. }
  50. int main()
  51. {
  52. int i,j,k,t,n,x,y,z;
  53. cin>>t;
  54. z=t;
  55. while(t--)
  56. {
  57. cin>>n;
  58. flag=0;
  59. vector<pt>v;
  60. for(i=0;i<n;i++)
  61. {
  62. cin>>x>>y;
  63. v.push_back({x,y,i});
  64. }
  65. vector<int>p=convex_hull(v);
  66. cout<<"Case "<<z-t<<":\n";
  67. if(flag==0)
  68. { cout<<"Impossible"<<endl;
  69. continue;
  70. }
  71. for(i=0;i<n;i++)
  72. cout<<p[i]<<" ";
  73. cout<<endl;
  74. }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment