Spoj TFOSS – CPP solution

Problem: http://www.spoj.com/problems/TFOSS/
Given N points, find the longest distance between any two points.
There are two important things to realize when solving the problem:
1) The pairs of such points the distance of which is the maximum are parts of the convex hull. Therefore, it is important to find the convex hull.
2) The size of convex hull is O(N). => We cannot still find the maximum distance naively. There are fast algorithms to find the longest dinstace in a convex polygon (diameter of a convex polygon) – in fact, there are O(N) such algorithms. However, they might be difficult to undestand or hard to implement. O(N logN) is just fast enough.

The idea is to iterate over all points of the convex hull and for each point find the other point for which we maximum distance in O(logN) time. We can use binary search.
Suppose that we are looking at the start of the convex polygon and we calculate the distances to every other vertex of the polygon. It would look something like:
1 6 9 12 55 99 221 88 66 45 33
The 221 would be the maximum. In general, you should realize that we have an ascending sequence and then a descending sequence. You can do binary search to find the peek.

Code:

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;

struct Point
{
    ll first;
    ll second;
    Point() {};
    Point (ll x, ll y) : first(x), second(y) {};
};


Point points[100002];
Point hull[200005];
size_t hullSize;

ll cross(const Point & A, const Point & B)
{
    return A.first * B.second - A.second*B.first;
}

Point operator - (const Point & A, const Point & B)
{
    return Point(A.first - B.first, A.second - B.second);
}

Point operator + (const Point & A, const Point & B)
{
    return Point(A.first + B.first, A.second + B.second);
}

ll dist(const Point & A, const Point & B)
{
    return (A.first-B.first)*(A.first-B.first) + (A.second-B.second)*(A.second-B.second);
}

bool comp(const Point & A, const Point & B)
{
    ll v1 = cross(A-points[0],B-points[0]);
    if (v1 > 0LL)
    {
        return true;
    }
    else if (v1 < 0LL)
    {
        return false;
    }
    else
    {
        return dist(A,points[0]) < dist(B,points[0]);
    }
}

ll hullSearch(int idx, int to)
{
    int l = idx+1;
    int r = to;
    ll s = 0LL;
    while (l <= r)
    {
        int mid = (l+r)>>1;
        ll l1 = dist(hull[mid-1], hull[idx]);
        ll l2 = dist(hull[mid], hull[idx]);
        ll l3 = dist(hull[mid+1], hull[idx]);
        s = max(l1, max(l2,l3));
        if (l1 < l2 && l2 > l3)
        {
            break;
        }
        else if (l1 <= l2 && l2 <= l3)
        {
            l = mid+1;
        }
        else
        {
            r = mid-1;
        }
    }
    return s;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        int idx = 0;
        for (int i = 0; i < n; ++i)
        {
            ll a,b;
            scanf("%lld%lld",&a,&b);
            points[i] = Point(a,b);
            if (b < points[0].second)
            {
                idx = i;
            }
            else if (b == points[0].second && a < points[0].first)
            {
                idx=i;
            }
        }
        swap(points[0], points[idx]);
        sort(points+1, points+n, comp);
        for (int i = 0; i < n; ++i)
        {
            while (hullSize > 1 && cross(hull[hullSize-1]-hull[hullSize-2], points[i]-hull[hullSize-2]) <= 0LL)
            {
                hullSize -= 1;
            }
            hull[hullSize++] = points[i];
        }
        for (int i = 0; i < hullSize; ++i)
        {
            hull[hullSize+i] = hull[i];
        }
        ll ans = 0LL;
        if (n == 1) hullSize=0;
        for (int i = 0; i < hullSize; ++i)
        {
            ll tmp = hullSearch(i, i+hullSize);
            if ( tmp > ans) ans = tmp;
        }
        printf("%lldn", ans);
        hullSize=0;
    }
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *