
Discussion A good example is ExtendableTriangles problem. Instead of counting extendable triangles directly, we just subtract a number of nonextendable triangles from a total number of triangles (which is N_{R}N_{G}N_{B} – a product of numbers of points of corresponding color). So, which triangles are nonextendable? The necessary, but not sufficient requirement for triangle to be nonextendable is that every its vertex is on a boundary of a convex hull of points of the same color. So for every of three colors we should construct a convex hull, and we should allow 180° angles here. So, if N is the maximum of a number of rows and a number of columns, a time complexity of this part is O(N^{3}) if we use Jarvis’s march – there are O(N^{2}) points, and O(N) points in the convex hull. Then for every triangle formed by three points of different convex hulls we should check if it is really nonextendable, i.e. if we change one of its vertices to another of the same color, its square doesn’t increase. We cannot do this directly because of that there are about 200 points of the same color in every of three convex hull in the worst case, so O(N^{4}) is too slow, but we can do some precalculation, namely, for every pair of points from two distinct convex hulls, we should find a maximal possible area of a triangle formed by these two and some third point from the third convex hull, and then check nonextendability of every triangle for O(1), so the whole time complexity is O(N^{3}). Here is the code:#include <string>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int c=50;
struct point {
int x,y;
point (int xx=0, int yy=0) {
x=xx;
y=yy;
}
};
vector<int> r[3];
vector<point> a[3];
bool b[c*c];
short msq[3][c*c][c*c];
int n,m;
inline int f(char h) {
if (h=='R') return 0; else
if (h=='G') return 1; else
return 2;
}
point operator  (const point &a, const point &b) {
return point(a.xb.x,a.yb.y);
}
int operator * (const point &a, const point &b) {
return a.x*b.x+a.y*b.y;
}
ll sqr(ll a) {
return a*a;
}
ll dist2(const point &a, const point &b) {
return sqr(a.xb.x)+sqr(a.yb.y);
}
inline int sign(int a) {
if (a>0) return 1; else
if (a<0) return 1; else
return 0;
}
bool better(const point &j, const point &i, const point &p, const point &pp) {
int r0i=(ip)*(ppp);
int r0j=(jp)*(ppp);
if (sign(r0i)!=sign(r0j)) return sign(r0i)<sign(r0j);
ll ri=sqr((ip)*(ppp))*dist2(p,pp)*dist2(j,p);
ll rj=sqr((jp)*(ppp))*dist2(p,pp)*dist2(i,p);
if (ri!=rj) if (r0i>0) return ri<rj; else return ri>rj; else return dist2(j,p)<dist2(i,p);
}
short sq(const point &a, const point &b, const point &c) {
return abs(a.x*(b.yc.y)+b.x*(c.ya.y)+c.x*(a.yb.y));
}
void get(int w) {
int i,j;
if (a[w].size()<=3) {
for (i=0; i<a[w].size(); ++i) r[w].push_back(i);
return;
}
r[w].push_back(0);
point p(a[w][0].x,a[w][0].y10);
memset(b,0,sizeof(b));
while (1) {
i=1;
for (j=0; j<a[w].size(); ++j)
if (j!=r[w][r[w].size()1] && !b[j] && (i==1  better(a[w][j],a[w][i],a[w][r[w][r[w].size()1]],p)))
i=j;
p=a[w][r[w][r[w].size()1]];
if (i==0) break;
b[i]=1;
r[w].push_back(i);
}
}
class ExtendableTriangles {
public:
int getCount (vector<string> s) {
int i,j,k;
n=s.size();
m=s[0].size();
int area;
for (i=0; i<3; ++i) a[i].clear();
for (i=0; i<3; ++i) r[i].clear();
for (i=0; i<n; ++i)
for (j=0; j<m; ++j)
a[f(s[i][j])].push_back(point(i,j));
for (i=0; i<3; ++i) get(i);
int ans=a[0].size()*a[1].size()*a[2].size();
for (i=0; i<r[0].size(); ++i) {
for (j=0; j<r[1].size(); ++j) {
msq[0][i][j]=0;
for (k=0; k<r[2].size(); ++k)
msq[0][i][j]=max(msq[0][i][j],sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]));
}
for (k=0; k<r[2].size(); ++k) {
msq[1][i][k]=0;
for (j=0; j<r[1].size(); ++j)
msq[1][i][k]=max(msq[1][i][k],sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]));
}
}
for (j=0; j<r[1].size(); ++j) {
for (k=0; k<r[2].size(); ++k) {
msq[2][j][k]=0;
for (i=0; i<r[0].size(); ++i)
msq[2][j][k]=max(msq[2][j][k],sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]));
}
}
for (i=0; i<r[0].size(); ++i)
for (j=0; j<r[1].size(); ++j)
for (k=0; k<r[2].size(); ++k) {
area=sq(a[0][r[0][i]],a[1][r[1][j]],a[2][r[2][k]]);
if (area<msq[0][i][j]  area<msq[1][i][k]  area<msq[2][j][k]) continue;
ans;
}
return ans;
}
};
Also there is an example of a hard problem where there is an easy part of constructing a convex hull – NCool. 