Advertisement
pasholnahuy

Untitled

Oct 18th, 2023
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.29 KB | None | 0 0
  1. #include <vector>
  2. #include <string>
  3. #include <cmath>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7.  
  8. struct Point{
  9. double x;
  10. double y;
  11. };
  12.  
  13. double scalar_product(Point p1, Point p2){
  14. return p1.x * p2.y - p2.x * p1.y;
  15. }
  16.  
  17. double length(Point p1, Point p2){
  18. return std::hypot(p1.x - p2.x, p1.y - p2.y);
  19. }
  20.  
  21. double angle(Point p1, Point p2, Point p3){
  22. Point v1 = {p1.x - p2.x, p1.y - p2.y};
  23. Point v2 = {p3.x - p2.x, p3.y - p2.y};
  24. return acos((scalar_product(v1, v2))/(length(p1, p2) * length(p2, p3)));
  25. }
  26. double polar_angle(Point p1, Point p2){
  27. return angle({-abs(p1.x) - 1, p1.x}, p1, p2);
  28. }
  29.  
  30. int main() {
  31. int n;
  32. cin >> n;
  33. vector<Point> coords(n);
  34. Point start = {1e5, 1e5};
  35. int cur_v;
  36. for (int i = 0; i < n; ++i){
  37. double x, y;
  38. cin >> x >> y;
  39. coords[i] = {x, y};
  40. if (start.y > coords[i].y || start.y == coords[i].y && start.x > coords[i].x){
  41. start = coords[i];
  42. cur_v = i;
  43. }
  44. }
  45. vector<int> convex_hull = {cur_v};
  46. Point mn = coords[cur_v];
  47. coords.erase(coords.begin() + cur_v);
  48. sort(coords.begin(), coords.end(), [&](const Point& a, const Point& b){ return polar_angle(start, a) < polar_angle(start, b);});
  49. double max_diff = 0;
  50.  
  51. return 0;
  52. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement