Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- const int counterClockwise = 1;
- const int clockwise = -1;
- using namespace std;
- struct Point{
- double x, y;
- bool operator<(const Point& point) const
- {
- return x < point.x;
- }
- };
- class BigBang
- {
- public:
- int n;
- vector<Point> a1;
- vector<Point> a2;
- BigBang();
- ~BigBang();
- int ccw(Point x, Point y, Point z);
- double cross(Point a, Point b);
- double andrew(vector<Point> points);
- double distance(Point a, Point b);
- // double findShortestPointPairDistance(vector<Point> points;);
- void exec();
- };
- BigBang::BigBang(){
- cin >> n;
- for (int i = 0; i < n; ++i)
- {
- Point p;
- cin >> p.x >> p.y;
- a1.push_back(p);
- }
- for (int i = 0; i < n; ++i)
- {
- Point p;
- cin >> p.x >> p.y;
- a2.push_back(p);
- }
- }
- BigBang::~BigBang(){}
- double BigBang::cross(Point a, Point b){
- return a.x * b.y - a.y * b.x;
- }
- int BigBang::ccw(Point a, Point b, Point c){
- b.x -= a.x;
- b.y -= a.y;
- c.x -= a.x;
- c.y -= a.y;
- if(cross(b, c) > 0) return counterClockwise ; // counter clockwise
- if(cross(b, c) < 0) return clockwise; // clockwise
- return 0;
- }
- // double BigBang::findShortestPointPairDistance(std::vector<Point> points){
- // }
- double BigBang::andrew(vector<Point> points){
- int k = 0;
- sort(points.begin(), points.end());
- vector<Point> convexPoints(2*n);
- // build lower
- for(int i = 0; i < n; ++i)
- {
- while(k >=2 && ccw(convexPoints[k-2], convexPoints[k-1], points[i]) != counterClockwise) k--;
- convexPoints[k++] = points[i];
- }
- //build upper
- for (int i = n-2, t = k+1; i >= 0; --i)
- {
- while(k >= t && ccw(convexPoints[k-2], convexPoints[k-1], points[i]) != counterClockwise) k--;
- convexPoints[k++] = points[i];
- }
- convexPoints.resize(k);
- double dis = 0;
- for (int i = 0; i < k-1; ++i)
- {
- dis += distance(points[i], points[i+1]);
- }
- return dis;
- }
- double BigBang::distance(Point a, Point b){
- return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
- }
- void BigBang::exec(){
- double ans = andrew(a2) / andrew(a1);
- printf("%.10f\n", ans);
- }
- int main(){
- BigBang bb = BigBang();
- bb.exec();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement