Is my convex hull code getting TLE due to atan() being slow, or is there some other reason?

Правка en1, от RedSnowstorm, 2022-02-26 01:51:05

I have written this convex hull code which uses the atan() function from cmatch in order to calculate the polar angle of a point(angle of it's vector with Ox), then sort the points by this value. My solution is currently getting TLE and I would like to know if this is due to the atan function being slow. I have searched and have not been able to find any information on its performance. If atan is the cause I would appreciate suggestions on easy ways to circumvent this problem. I know there are ways to do convex hull without atan, it's just that calculating this is a pretty intuitive and easy way for me and I'm curious if there's any way to do it efficiently. Here is the code:

#include <bits/stdc++.h>
#define double long double
using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

struct Point {
    double x,y;

    bool operator < (const Point other) const {
        if (y != other.y) {
            return y < other.y;
        }
        return x < other.x;
    }

    Point operator - (const Point other) const {
        return Point{x - other.x , y - other.y};
    }
};

double angle(Point p) { /// returns in radians the angle of the Point
    if (p.x == 0) {
        if (p.y == 0) return 0;
        if (p.y > 0) return M_PI/2;
        if (p.y < 0) return M_PI + M_PI / 2;
    }
    if (p.x > 0 && p.y > 0) {
        return atan(p.y / p.x);
    } else if ( p.x > 0 && p.y < 0) {
        return atan(p.y / p.x) + 2 * M_PI; /// pi = 180 degrees
    } else {
        return atan(p.y / p.x) + M_PI;
    }
}

bool rightTurn(Point a, Point b, Point c) {
    return angle(b - a) > angle(c - b);
}
vector<Point> pt;
int n,i;
double x,y;
vector<Point> res;
Point lowLeft;

vector<Point> convexHull() {

    lowLeft = pt[1];
    for (i = 2; i <= n; i++) {
        if (pt[i] < lowLeft) {
            lowLeft = pt[i];
        }
    }
    sort(pt.begin() + 1, pt.end() , [&](Point a, Point b) {
        ///we move everyone down by this low left point, then sort this increasing by their angle.
        return angle(a - lowLeft) < angle(b - lowLeft);
    });

    for (i = 1; i <= n; i++) {
        while(res.size() >= 2 && rightTurn(res[(int)res.size() - 2] , res[(int)res.size() - 1] , pt[i])) {
            res.pop_back();
        }
        res.push_back(pt[i]);
    }
    return res;
}

int main() {

    in >> n;
    pt.resize(n + 1);
    for (i = 1; i <= n; i++) {
        in >> x >> y;
        pt[i] = {x,y};
    }


    convexHull();

    out << fixed << setprecision(12);
    out << res.size() << "\n";
    for (auto k : res) {
        out << k.x << " " << k.y << "\n";
    }
    out << "\n";
}


Теги convex hull, atan, geometry

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский RedSnowstorm 2022-02-26 01:53:42 159
en1 Английский RedSnowstorm 2022-02-26 01:51:05 2848 Initial revision (published)