JMK no matter what

A simple geometry 250, counting 550 and quite tricky 950. I thought I didn't have a chance writing both 550 and 950 in time, and wasted some time looking and thinking about both problems. I finally went for 550 - that proved to be easier than I thought. So the score is not great... but anyway.

Ah, and the source code for this match was committed with revision 1000 of my personal SVN repository.

250 MaxTriangles

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

const int M = 44722;
struct MaxTriangle 
{
    set<int> sqs;
    VI possibleX(int R2)
    {
        VI ret;
        REP(x,M) 
        {
            int x2 = x*x, y2 = R2-x2;
            if(sqs.count(y2)) ret.pb(x);
        }
        return ret;
    }
    double getY(double dist, double x)
    {
        return sqrt(dist - x*x); 
    }
    double calculateArea( int A, int B ) 
    {
        REP(i,M) sqs.insert(i*i);
        vector<int> xA = possibleX(A);
        vector<int> xB = possibleX(B);
        double ret = -1;
        REP(i,xA.sz) REP(j,xB.sz)
        {
            ret = max(ret, (xA[i] * getY(B, xB[j]) + getY(A, xA[i]) * xB[j])/2);
        }
        return ret;
    }
};

500 HexagonBattlefield

Apart from the fact that it uses hexagonal grids, 550 is just plain standard exponential DP.

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

typedef pair<int,int> point;
int cache[17][(1<<16)+10];
const int dx[6] = { 1, 0, -1 };
const int dy[6] = { 0, -1, -1 };
const int BIAS = 8;
const int M = 2000000011;
struct HexagonalBattlefield 
{
    vector<point> p;
    int bufA[17], bufB[17];
    int *minRow, *maxRow;
    VI next[200];
    map<point,int> index;    
    VI taken;
    int N;

    int go(int y, int x, int loc)
    {
        if(y < -(N-1)) return 1;
        if(x > maxRow[y]) return go(y-1, minRow[y-1], loc);
        int mask = -1;
        if(x == minRow[y])
        {
            mask = 0;
            int rw = maxRow[y]+1-minRow[y];
            REP(i,rw)
                mask = mask * 2 + taken[i+loc];
            if(cache[y+BIAS][mask] != -1) return cache[y+BIAS][mask];
        }
        ll ret = 0;
        if(taken[loc]) 
            ret = go(y, x+1, loc+1);
        else
        {
            REP(i,next[loc].sz)
            {
                int other = next[loc][i];
                if(taken[other]) continue;
                taken[other] = 1;
                (ret += go(y, x+1, loc+1)) %= M;
                taken[other] = 0;
            }
        }
        if(mask != -1) cache[y+BIAS][mask] = ret;
        return ret;
    }

    int countArrangements( vector <int> X, vector <int> Y, int N_ ) 
    {
        N = N_;
        minRow = bufA + BIAS;
        maxRow = bufB + BIAS;
        // gen graph
        for(int y = N-1; y >= -(N-1); --y)
        {
            int rowWidth = N+N-1 - abs(y);
            minRow[y] = max(-(N-1)+y, -(N-1));
            maxRow[y] = minRow[y] + rowWidth - 1;
            printf("minRow[%d] = %d, maxRow[%d] = %d\n", y, minRow[y], y, maxRow[y]);
            FOR(x,minRow[y],maxRow[y]+1)
            {
                p.push_back(point(y, x));
                index[p.back()] = p.sz-1;
            }
        }
        REP(i,p.sz) 
        {
            //printf("point #%d (%d,%d)\n", i, p[i].first, p[i].second);
            REP(k,3)
            {
                point q = point(p[i].first + dy[k], p[i].second + dx[k]);
                if(index.count(q))
                {
                    next[i].pb(index[q]);
                    //printf("\tnext %d (%d,%d)\n", index[q], q.first, q.second);
                }
            }
        }
        CLEAR(cache,-1);
        taken.assign(p.sz, 0);
        REP(i,X.sz)
        {
            point q(Y[i], X[i]);
            assert(index.count(q));
            taken[index[q]] = 1;
        }
        return go(N-1, minRow[N-1], 0);
    }
};