### RedSnowstorm's blog

By RedSnowstorm, history, 15 months ago,

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;
} 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;

vector<Point> convexHull() {
vector<Point> res;

Point lowLeft = pt[1];
for (int 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 it's angle.
return angle(a - lowLeft) < angle(b - lowLeft);
});

for (int 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 (int i = 1; i <= n; i++) {
double x,y;
in >> x >> y;
pt[i] = {x,y};
}

auto hull = convexHull();

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


• -9

 » 15 months ago, # |   +3 TL & restraints please?
•  » » 15 months ago, # ^ |   0 3 ≤ N ≤ 120.000 -1.000.000.000 ≤ Xi,Yi ≤ 1.000.000.000 No 3 points are on the same line. 0.5 seconds time limit (the judge is a bit slower than CF though.)
 » 15 months ago, # |   +4 I might be very stupid, but why don't you use ios::sync_with_stdio(false); and cin.tie(nullptr); in this code?
•  » » 15 months ago, # ^ |   0 Because this code uses fle input and output so I don't think that would do anything.
 » 15 months ago, # |   0 Don't read double directly from istream. Tracking where the notation of the number ends is extremely slow due to the complicated format. Instead, read it to a temporary string.
•  » » 15 months ago, # ^ | ← Rev. 2 →   -8 I changed input to this and the speed didn't really change: string N; in >> N; n = stold(N);string X,Y; in >> X >> Y; x = stold(X); y = stold(Y);I also changed output to using to_string()
 » 15 months ago, # |   +5 The problem with your code is probably with input like others said. However, convex hull code can be much shorter and without atan... Codevector v, a; pi operator+(pi x, pi y){ return {x.f + y.f, x.s + y.s};} pi operator-(pi x, pi y){ return {x.f - y.f, x.s - y.s};} ll operator*(pi x, pi y){ return x.f * y.f + x.s * y.s;} ll operator^(pi x, pi y){ return x.f * y.s - x.s * y.f;} ll crs(pi x, pi y, pi z){ return (x - z) ^ (y - z);} ll dot(pi x, pi y, pi z){ return (x - z) * (y - z);} //get convex hull swap(a, *min_element(a.begin(), a.end())); sort(a.begin() + 1, a.end(), [&](pi x, pi y){ ll z = crs(x, y, a[0]); return z ? z > 0 : dot(x, x, a[0]) < dot(y, y, a[0]); }); for(int j = 0; j <= n; j++){ while(v.size() > 1 + (j == n) && crs(v.end()[-2], v.back(), a[j % n]) <= 0){ v.pop_back(); } if(j < n) v.push_back(a[j]); }