Spoj Anttt – CPP solution

Link: http://www.spoj.com/problems/ANTTT/
Idea:
Create a graph of the intersecting lines and use dfs/bfs to find whether a path exists from one node to another. For the intersection part there are two possible ways I know:
1) write out equations for the lines and find the formula for the Y (or X) cordinate and then check whether the point is part of the segment. This is however harder and slower to right with some cases to consider. For example the line x=0.
2) just use standard vector operations. If you are given the lines A-B and C-D. Chech whether A is on one side of C-D and if B is on the other. Then check whether C and D are on opposite sides of A-B. In this case they collide. If we also consider the case where one of the points can lie on the segments, then we can to also consider the case: 1 1 3 3, 4 4 5 5. I.e. when they are parallel. Then you have to also check for the bounds.

When I was at high school, I used to write the first technique and it worked out well. I learned about the second while I was doing USACO.

#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

struct Point {
    ll x,y;
    Point() {};
    Point(ll _x, ll _y) : x(_x), y(_y) {};
};

struct Line {
    Point from,to;
    Line() {};
    Line(const Point & _from, const Point & _to) : from(_from), to(_to) {};
};

Point operator -(const Point & A, const Point & B) {
    return Point(A.x-B.x, A.y-B.y);
}

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

bool onOneSide(const Line & A, const Line & B) {
    ll v1 = cross(B.from - A.from, A.to - B.from);
    ll v2 = cross(B.to - A.from, A.to - B.to);

    if(v1 == 0LL && v2 == 0LL) {
        if (A.to.x < B.from.x) return false;
        if (A.from.x > B.to.x) return false;
    }
    return (v1 <= 0LL && v2 >=0LL) || (v1 >=0LL && v2 <= 0LL);
}

bool intersect(const Line & A, const Line & B) {
    return onOneSide(A,B) && onOneSide(B,A);
}

int nb[1001][1001];
int nbSz[1001];
int used[1001];
Line lines[1001];
int destination;
int q;

void dfs(int u) {
    if (used[u]==q) return;
    if (destination==-1) return;
    if (u == destination) destination = -1;
    used[u] = q;
    for (int i = 0; i < nbSz[u]; ++i) {
        dfs(nb[u][i]);
    }
}

void cl(int n) {
    for (int i = 1; i<=n; ++i) nbSz[i]=0, used[i]=0;
}

void addNb(int A, int B) {
    nb[A][nbSz[A]++] = B;
    nb[B][nbSz[B]++] = A;
}

int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i = 0; i < n; ++i) {
            ll x1,x2,y1,y2;
            scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
            if (x1 > x2) {
                swap(x1,x2);
                swap(y1,y2);
            }
            lines[i+1] = Line(Point(x1,y1),Point(x2,y2));
        }
        for (int i = 1; i<=n; ++i) {
            for (int j = i+1; j<=n; ++j) {
                if (intersect(lines[i], lines[j])) {
                        addNb(i,j);
                }
            }
        }
        for (q = 1; q <= m; ++q) {
            int a,b;
            scanf("%d%d",&a,&b);
            destination = b;
            dfs(a);
            if (destination == -1) {
                printf("YESn");
            } else {
                printf("NOn");
            }
        }
        cl(n);
    }
    return 0;
}

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

Spoj GEOPROB – Cpp solution

The idea is first express A as a function of B, C and D. It’s quite easy to see that the answer would be:
A = 2*C – B – D.
Since the numbers can be quite big, you will have to write your own methods for addition and subtraction of big numbers (200 digits).

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int>  b(201),c(201),d(201);

void print(const vector<int> & V) {
    for (int i = 0; i < V.size(); ++i) {
        printf("%d", V[i]);
    }
    printf("n");
}

void clean(vector<int> & V) {
    while(V[0] == 0) V.erase(V.begin());
}

vector<int> operator +(const vector<int> & A, const vector<int> & B) {
    vector<int> Arev = A, Brev = B;
    reverse(Arev.begin(), Arev.end());
    reverse(Brev.begin(), Brev.end());
    vector<int> res;
    int sz = (max(Arev.size(), Brev.size()));
    res.resize(sz+1);

    for (int i = 0; i < sz; ++i) {
        int f1=0,f2=0,f3 = 0;
        if (Arev.size() > i) {
            f1 = Arev[i];
        }
        if (Brev.size() > i) {
            f2 = Brev[i];
        }
        f3 = res[i];
        int f4 = f1+f2+f3;
        int dig = f4%10;
        int se = (f4/10)%10;
        res[i] = dig;
        res[i+1] = se;
    }
    reverse(res.begin(), res.end());
    return res;

}

vector<int> operator -(const vector<int> & A, const vector<int> & B) {
    vector<int> Arev = A, Brev = B;
    reverse(Arev.begin(), Arev.end());
    reverse(Brev.begin(), Brev.end());
    vector<int> res;
    int sz = (max(Arev.size(), Brev.size()));
    res.resize(sz);
    for (int i = 0; i < sz; ++i) {
        int f1 = 0, f2 = 0;
        if (Arev.size() > i) {
            f1 = Arev[i];
        }
        if (Brev.size() > i) {
            f2 = Brev[i];
        }
        f2 += res[i];
        res[i] = 0;
        int f3 = (f1-f2);
        if (f3 < 0) {
            f3 += 10;
            res[i] = f3%10;
            res[i+1] = 1;
        } else {
            res[i] = f3;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

void readS(vector<int> * buf) {
    buf->clear();
    buf->reserve(201);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        buf->push_back(s[i]-'0');
    }
}

void read() {
    readS(&b);
    readS(&c);
    readS(&d);
}

void answer() {
    vector<int> dc = c+c;
    clean(dc);
    dc = dc - b;
    clean(dc);
    dc = dc - d;
    clean(dc);
    print(dc);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        read();
        answer();
    }
    return 0;
}

Spoj STONE – CPP solution

I just found a problem I wasn’t able to solve in the past. It seams I have tried to solve it by summing all of the x coordinates and then dividing them by the number of points.

#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
using namespace std;

#define pii pair<int,int>

vector<pii> points;

double round2(double number) {
    number *= 100;
    return round(number)/100.0;
}

double crossProduct(pii a, pii b) {
    return a.first * b.second - b.first*a.second;
}

double signedArea() {
    double area = 0.0;
    int n = points.size();
    for (int i = 0; i <n; ++i) {
        area += crossProduct(points[i], points[(i+1)%n]);
    }
    return 0.5*area;
}

double sigmaX() {
    double sum = 0.0;
    int n = points.size();
    for (int i = 0; i < n; ++i) {
        sum += (points[i].first + points[(i+1)%n].first)*crossProduct(points[i], points[(i+1)%n]);
    }
    return sum;
}

double sigmaY() {
    double sum = 0.0;
    int n = points.size();
    for (int i = 0; i < n; ++i) {
        sum += (points[i].second + points[(i+1)%n].second)*crossProduct(points[i], points[(i+1)%n]);
    }
    return sum;
}

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
        int n;
        points.clear();
        scanf("%d",&n);
        int a,b;
        double sumx=0,sumy=0;
        for (int k=0; k < n; ++k) {
            scanf("%d%d",&a,&b);
            points.push_back(make_pair(a,b));
        }
        double area = signedArea();
        double cx = (sigmaX()/6.0)/area;
        double cy = (sigmaY()/6.0)/area;
        printf("%.2f %.2fn", round2(cx), round2(cy));

    }

}

USACO 3.4 Closed Fences – CPP solution

Checking whether the fence is valid is fairly simple. We just check whether one line segment intersects some other line segment (excluding the neighbor segments).
Afterwards, it is the tricky part. We have to find all the visible segments. How can we do that?
Let the observer be the point P and some random line segment be Q where its end points are respectively A and B.
We will partition the line in 250 parts (from A + EPS to B – EPS). Then we will build every possible line to the part points (i.e. the line P – (A + EPS*2)). Then we will just check whether the newly created line intersects some of the fence segments. If it doesn’t, the line segment Q is visible to P.
And also, we will have to use in our calculations as well. For example, in our check whether the value is nearly 0.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int n;

#define EPS 0.05
#define PARTITION 250.0

struct point {
    double x;
    double y;
};


struct line {
    point a;
    point b;
};

FILE * in, * out;

point p[202];
line l[202];
point observer;

vector<line> ans;

point makePoint(double x, double y) {
    point tmp;
    tmp.x = x;
    tmp.y = y;
    return tmp;
}

line makeLine(point a, point b) {
    line tmp;
    tmp.a = a;
    tmp.b = b;
    return tmp;
}

point operator -(point a, point b) {
    a.x -= b.x;
    a.y -= b.y;
    return a;
}

point operator +(point a, point b) {
    a.x += b.x;
    a.y += b.y;
    return a;
}

line getOrderedLine (line a) {
    if (a.a.y > a.b.y) {
        point tmp = a.a;
        a.a = a.b;
        a.b = tmp;
    }
    if (a.a.y == a.b.y && a.a.x > a.b.x) {
        point tmp = a.a;
        a.a = a.b;
        a.b = tmp;
    }
    return a;
}

double cross(point a, point b) {
    return a.x*b.y - a.y*b.x;
}

bool nearlyZero(double value) {
    if (value>=-EPS && value<=0) {
        return true;
    }
    return false;
}

void printPoint (point a) {
    cout << "(" << a.x << " " << a.y << ")";
}

void printLine(line a) {
    printPoint(a.a);
    cout << " - ";
    printPoint(a.b);
    cout << endl;
}

bool segmentIntersect(line a, line b) {
    a = getOrderedLine(a);
    b = getOrderedLine(b);
    double first = cross(a.b-a.a,b.a-a.a)*cross(a.b-a.a,b.b-a.a);
    double second = cross(b.b-b.a,a.a-b.a)*cross(b.b-b.a,a.b-b.a);
    if (nearlyZero(first) && nearlyZero(second)) {
        if (a.a.y!=a.b.y && b.a.y != b.b.y) {
            if (((a.a.y <= b.a.y && a.b.y >= b.a.y) || (b.a.y <= a.a.y && a.a.y <= b.b.y))) return true;
        } else {
            if ((a.a.x <= b.a.x && a.b.x >= b.a.x) || (b.a.x <= a.a.x && a.a.x <= b.b.x)) return true;
        }
        return false;
    }
    if (first > EPS) return false;
    if (second > EPS) return false;

    return true;
}


bool canSeeLine(line a, int ignoreIndex) {
    point delta = makePoint((a.b.x-a.a.x)/PARTITION, (a.b.y-a.a.y)/PARTITION);
    line cpy = a;
    for (int i = 0; i < PARTITION-1; ++i) {
        a.a = a.a+delta;
        line check = makeLine(observer, a.a);

        bool blocked = false;
        int j = 0;
        for (j = 0; j < n && !blocked; ++j) {
            if (j == ignoreIndex) continue;
            if (segmentIntersect(l[j],check)) {
                blocked = true;
            }
        }
        if (!blocked) {
            if (ignoreIndex==19) {
                printLine(cpy);
                printLine(a);
            }
            return true;
        }

    }
    return false;
}

void solve() {
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+2; j < n-1; ++j) {
            if (segmentIntersect(l[i],l[j])) {
                printLine(l[i]);
                printLine(l[j]);
                return;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (canSeeLine(getOrderedLine(l[i]),i)) {
            ans.push_back(l[i]);
        }
    }
}

int getPointIndex(point a) {
    for (int i = 0; i < n; ++i) {
        if (a.x == p[i].x && a.y == p[i].y) return i;
    }
}

bool comparator(line a, line b) {
    int indexA = getPointIndex(a.b);
    int indexB = getPointIndex(b.b);
    if (indexA != indexB) return indexA < indexB;
    return getPointIndex(a.a) < getPointIndex(b.a);
}

int main() {
    in = fopen("fence4.in","r");
    int a,b;
    fscanf(in,"%d%d%d",&n,&a,&b);
    observer = makePoint(a,b);
    for (int i = 0; i < n; ++i) {
        fscanf(in,"%d %d",&a,&b);
        p[i] = makePoint((double)a,(double)b);
    }
    p[n] = p[0];
    for (int i = 0; i < n-1; ++i) {
       l[i] = makeLine(p[i],p[i+1]);
    }
    l[n-1] = makeLine(p[0],p[n-1]);
    fclose(in);
    solve();
    out = fopen("fence4.out","w");
    if (ans.size() == 0) {
        fprintf(out, "NOFENCEn");
    } else {
        fprintf(out,"%dn", ans.size());
        sort(ans.begin(),ans.end(), comparator);
        for (int i = 0; i < ans.size(); ++i) {
            fprintf(out,"%d %d %d %dn",(int)ans[i].a.x,(int)ans[i].a.y,(int)ans[i].b.x,(int)ans[i].b.y);
        }
    }
    fclose(out);
    return 0;
}

USACO 3.4 Electric Fence – CPP solution

This is an interesting problem which I was not able to solve by the first try and I will shortly explain why after I explain what is my solution ( O(N) time where N is the maximum Y value).
We get the information about the two lines which make the triangle. By information, I mean the slope and the C value. (y = slope*x + C).
The we just iterate from 0 to the maximum Y value of our triangle (the pivot point) and we check what is the possible leftest value and accordingly rightest value. Then we add the value count (right-left+1) to our COUNT variable.
Everything seems fine and the solution yields just O(N) time where N is at maximum 32 000 (a fairly small number).

You may as well try the solution on your really cool computer with the latest 64bit processor and you will probably always get the right answer. But after you submit it, you will get a wrong answer warning from USACO. How come? Everything works correct on your computer? Well, it is mostly because your processor is 64bit and their maybe 32bit? I don’t really know and I do not want to get into really technical stuff.

The problem is with the decimal part. For example, we may receive for rights X value 9.999998 which should be actually 10.0 or it might be even 10.01 or even more. We will add an EPS value (a very small number) to check whether one value equals another. For example, 9.99998 will equal 10.00 and 10.0001 will equal 10.00.

Just now our program seems to work flawlessly.

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

#define INF -99999.0
#define EPS 0.00001

double n,m,p;
long long cnt = 0;

struct line {
    double k;
    double c;
};

line leftLine,rightLine;

line makeLine (double k, double c) {
    line tmp;
    tmp.k = k;
    tmp.c = c;
    return tmp;
}

double slope(double x1, double y1, double x2, double y2) {
    if (x2-x1==0.0) return INF;
    return (y2-y1)/(x2-x1);
}

double properRound(double value) {
    double ceiled = ceil(value);
    double floored = floor(value);
    if (value-EPS <= floored) return floored;
    if (value+EPS >= ceiled) return ceiled;
    return value;
}

int getLeft(int y) {
    if (leftLine.k == INF) {
        return 1;
    }
    double pos = properRound((y-leftLine.c)/leftLine.k);
    return floor(pos + 1.0);
}

int getRight(int y) {
    double pos = properRound((y-rightLine.c)/rightLine.k);
    return ceil(pos-1.0);
}

int getCount(int y) {
    return getRight(y)-getLeft(y)+1;
}

void solve() {
    leftLine = makeLine(slope(0.0,0.0,n,m),0.0);
    rightLine = makeLine(slope(p,0.0,n,m),-slope(p,0.0,n,m)*p);
    for (double i = 1.0; i < m; i+=1.0) {
        cnt += getCount(i);
    }
}

int main() {
    ifstream in("fence9.in");
    in >> n >> m >> p;
    in.close();
    solve();
    ofstream out("fence9.out");
    out << cnt << endl;
    out.close();
    return 0;
}