Contest Template

C++ contest coding template. Edit:5.

/*
USER: zobayer
TASK: template
ALGO: template
*/
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ALL(c) c.begin(), c.end()
#define SIZE(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 __int64
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const double BIG = 1e19;
const int INF = 0x7f7f7f7f;

int main() {
    //READ("in.txt");
    //WRITE("out.txt");
    return 0;
}

Segment-Circle Intersection

This is a sample code which verifies whether a given Circle and Segment intersects or not.

/*
**  Verifies the intersection of a segment and a circle
**  The line segment is defined from points p1 to p2
**  The circle is of radius r and centered at point c
**  There are potentially two points of intersection given by
**  p = p1 + mu1 (p2 - p1)
**  p = p1 + mu2 (p2 - p1)
**  mu1 and mu2 are updated via reference
**  Return FALSE if the segment doesn't intersect the circle
*/
bool cross(POINT p1, POINT p2, CIRCLE p, double &mu1, double &mu2) {
    double a, b, c, d;
    POINT t;
    t.x = p2.x - p1.x;
    t.y = p2.y - p1.y;
    a = sq(t.x) + sq(t.y);
    b = 2.0 * (t.x * (p1.x - p.c.x) + t.y * (p1.y - p.c.y));
    c = sq(p.c.x) + sq(p.c.y);
    c += sq(p1.x) + sq(p1.y);
    c -= 2.0 * (p.c.x * p1.x + p.c.y * p1.y);
    c -= sq(p.r);
    d = b * b - 4 * a * c;
    if(fabs(a) < eps || d < -eps) {
        mu1 = mu2 = 0.0;
        return false;
    }
    mu1 = (-b + sqrt(d)) / (2.0 * a);
    mu2 = (-b - sqrt(d)) / (2.0 * a);
    return true;
}

SPOJ Hints

Thanks to the Japanese boy, from whom I got this list. But unfortunately I could not read his name.. (Sorry! I can't read Japanese language.)

I've edited the list and added some myself (uploaded on Google Docs). This list is going to updated time by time...

Here is the file, have a look.
[Last updated: Thursday, November 12, 2009]

If any mistake is found, please comment out here. Thanks...