Advertisement
Guest User

Untitled

a guest
Dec 8th, 2016
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. const int counterClockwise = 1;
  6. const int clockwise = -1;
  7.  
  8. using namespace std;
  9.  
  10. struct Point{
  11. double x, y;
  12. bool operator<(const Point& point) const
  13. {
  14. return x < point.x;
  15. }
  16. };
  17.  
  18. class BigBang
  19. {
  20. public:
  21. int n;
  22. vector<Point> a1;
  23. vector<Point> a2;
  24. BigBang();
  25. ~BigBang();
  26. int ccw(Point x, Point y, Point z);
  27. double cross(Point a, Point b);
  28. double andrew(vector<Point> points);
  29. double distance(Point a, Point b);
  30. // double findShortestPointPairDistance(vector<Point> points;);
  31. void exec();
  32. };
  33.  
  34.  
  35. BigBang::BigBang(){
  36. cin >> n;
  37. for (int i = 0; i < n; ++i)
  38. {
  39. Point p;
  40. cin >> p.x >> p.y;
  41. a1.push_back(p);
  42. }
  43.  
  44. for (int i = 0; i < n; ++i)
  45. {
  46. Point p;
  47. cin >> p.x >> p.y;
  48. a2.push_back(p);
  49. }
  50.  
  51. }
  52.  
  53. BigBang::~BigBang(){}
  54.  
  55. double BigBang::cross(Point a, Point b){
  56. return a.x * b.y - a.y * b.x;
  57. }
  58.  
  59. int BigBang::ccw(Point a, Point b, Point c){
  60. b.x -= a.x;
  61. b.y -= a.y;
  62. c.x -= a.x;
  63. c.y -= a.y;
  64. if(cross(b, c) > 0) return counterClockwise ; // counter clockwise
  65. if(cross(b, c) < 0) return clockwise; // clockwise
  66. return 0;
  67. }
  68.  
  69. // double BigBang::findShortestPointPairDistance(std::vector<Point> points){
  70.  
  71. // }
  72.  
  73. double BigBang::andrew(vector<Point> points){
  74. int k = 0;
  75. sort(points.begin(), points.end());
  76. vector<Point> convexPoints(2*n);
  77. // build lower
  78. for(int i = 0; i < n; ++i)
  79. {
  80. while(k >=2 && ccw(convexPoints[k-2], convexPoints[k-1], points[i]) != counterClockwise) k--;
  81. convexPoints[k++] = points[i];
  82. }
  83. //build upper
  84. for (int i = n-2, t = k+1; i >= 0; --i)
  85. {
  86. while(k >= t && ccw(convexPoints[k-2], convexPoints[k-1], points[i]) != counterClockwise) k--;
  87. convexPoints[k++] = points[i];
  88. }
  89. convexPoints.resize(k);
  90. double dis = 0;
  91. for (int i = 0; i < k-1; ++i)
  92. {
  93. dis += distance(points[i], points[i+1]);
  94. }
  95. return dis;
  96. }
  97.  
  98. double BigBang::distance(Point a, Point b){
  99. return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
  100. }
  101.  
  102. void BigBang::exec(){
  103. double ans = andrew(a2) / andrew(a1);
  104. printf("%.10f\n", ans);
  105.  
  106. }
  107.  
  108. int main(){
  109. BigBang bb = BigBang();
  110. bb.exec();
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement