CF #598 C. Nearest vectors

Using atan2() vs atan()

Problem Statement : https://codeforces.com/contest/598/problem/C

The entire problem is based on the fact of using long doubles instead of doubles for calculating angles. You must try yourself and you will soon figure out that you need to compute the angle of each vector from the principal axis.

Now, there are two possible ways of doing it. The first is computing the value of y/x and using atan(y/x) to compute the angle. The second and best option is using atan2(y,x) and using this angle.

The range of atan(y/x) is : -PI/2 to +PI/2

The range of atan2(y,x) is : -PI to PI

The cplusplus links are:

atan2 – http://www.cplusplus.com/reference/cmath/atan2/

atan – http://www.cplusplus.com/reference/cmath/atan/

Give this a read once – https://stackoverflow.com/questions/283406/what-is-the-difference-between-atan-and-atan2-in-c

void solve()
{
	ll n;
	cin >> n;
	vector<pair<long double,ll>> v;
    rep(i,1,n+1){
        long double x,y;
        cin >> x >> y;
        long double par;
        long double ang;
        if(y == 0){
            if ( x < 0) ang = PI;
            else ang = 0;
        }
        else if (x == 0){
            if (y < 0) ang = 3*PI/2;
            else ang = PI/2;
        }
        else{
            ang = atan2(y,x);
        }
        if (ang < 0) ang += 2*PI;
        v.PB({ang,i});
    }
    sort(all(v));
    long double minm = inf;
    pair<ll,ll> p;
    rep(i,0,n){
        // cout << v[i].F << endl;
        if (i == n-1){
            long double mn = v[i].F-v[0].F;
            if (mn > PI) mn = 2*PI - mn;
            if (mn < minm){
                minm = mn;
                p.F = v[i].S;
                p.S = v[0].S;
            }
            continue;
        }
        long double mn = v[i+1].F-v[i].F;
        if (mn > PI) mn = 2*PI - mn;
        if (mn < minm){
            minm = mn;
            p.F = v[i].S;
            p.S = v[i+1].S;
        }
    }
    cout << p.F << " " << p.S << endl;
    
}

Leave a Reply