Artifact Content
Not logged in

Artifact 5c2f54954f3e8b6d1befc50b4d0c002af35e1951


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<int> CMP;

double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }

int ccw(const CMP& a, CMP b, CMP c) {
	b -= a; c -= a;
	if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
	if( outer_prod(b,c) < 0 ) return -1; // clockwise
	if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line
	if( norm(b) < norm(c) )   return -2; // a--b--c on line
	return 0;
}

bool byX( const CMP& a, const CMP& b ) {
	if( a.real() != b.real() )
		return a.real() < b.real();
	return a.imag() < b.imag();
}

vector<CMP> convex_hull( vector<CMP> p )
{
	//#define IS_RIGHT <0   // skip on-line verts
	#define IS_RIGHT ==-1 // take all

	sort(p.begin(), p.end(), &byX);

	vector<CMP> ans;
	for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right
		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
			ans.pop_back();
	if( ans.size() == p.size() )
		return ans;
	for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left
		while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT )
			ans.pop_back();
	ans.pop_back();
	return ans;
}

int area(const CMP& a, const CMP& b, const CMP& c)
{
	return (int) abs( outer_prod(b-a,c-a) );
}

class ExtendableTriangles {
public:
	int getCount(vector <string> grid) 
	{
		vector<CMP> r, g, b;
		for(int y=0; y<grid.size(); ++y)
			for(int x=0; x<grid[0].size(); ++x)
				(grid[y][x]=='R' ? r : grid[y][x]=='G' ? g : b).push_back( CMP(y,x) );

		int cnt = r.size() * g.size() * b.size();

		r = convex_hull(r);
		g = convex_hull(g);
		b = convex_hull(b);

		bool (*ext)[200][200] = (bool(*)[200][200])calloc(200*200*200, 1);
		for(int i=0; i<r.size(); ++i)
			for(int j=0; j<g.size(); ++j)
			{
				int ma = -1;
				for(int k=0; k<b.size(); ++k)
					ma = max(ma, area(r[i], g[j], b[k]));
				for(int k=0; k<b.size(); ++k)
					if( area(r[i], g[j], b[k]) < ma )
						ext[i][j][k] = true;
			}
		for(int j=0; j<g.size(); ++j)
			for(int k=0; k<b.size(); ++k)
			{
				int ma = -1;
				for(int i=0; i<r.size(); ++i)
					ma = max(ma, area(r[i], g[j], b[k]));
				for(int i=0; i<r.size(); ++i)
					if( area(r[i], g[j], b[k]) < ma )
						ext[i][j][k] = true;
			}
		for(int k=0; k<b.size(); ++k)
			for(int i=0; i<r.size(); ++i)
			{
				int ma = -1;
				for(int j=0; j<g.size(); ++j)
					ma = max(ma, area(r[i], g[j], b[k]));
				for(int j=0; j<g.size(); ++j)
					if( area(r[i], g[j], b[k]) < ma )
						ext[i][j][k] = true;
			}
		for(int i=0; i<r.size(); ++i)
			for(int j=0; j<g.size(); ++j)
				for(int k=0; k<b.size(); ++k)
					if( !ext[i][j][k] )
						--cnt;
		free(ext);
		return cnt;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);

int Test_(Case_<0>) {
	string grid_[] = {"RGB"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 0; 
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }
int Test_(Case_<1>) {
	string grid_[] = {"RGB",
 "RGB"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 6; 
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }
int Test_(Case_<2>) {
	string grid_[] = {"RRRRRRRR",
 "GGGGBBBB",
 "RRRRRRRR"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 240; 
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }
int Test_(Case_<3>) {
	string grid_[] = {"RBRBRBRB",
 "BRBRBRBR",
 "RBRBRBRB",
 "BRBRBRBR",
 "RRRRRRRR",
 "BBBBBBBB",
 "RRRRBBBB",
 "BBBBRRRR"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 0; 
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }
int Test_(Case_<4>) {
	string grid_[] = {"RGB",
 "RBG",
 "GRB",
 "GBR",
 "BRG",
 "BGR"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 208; 
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }
int Test_(Case_<5>) {
	string grid_[] = {"BBRRBBGRBG"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 0; 
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }
int Test_(Case_<6>) {
	string grid_[] = {"RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR", "RGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGR", "RGBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBGRGBRBRGBBBBGBRBRBRGRGBBBBRRBGGRGRBGBBBBBGR", "RGBBBGRGRBRGBRGBRGBRGBGGBRBRBRGBRGBRGGBRBBBBBBBBGR", "RGBBBRGBRBRBRGBRGBRBRBRBRGBRGGGGRRBBRGBBBGRRGRBBGR", "RGBBRRGBRBRBRGGBRGRRGRGBRGBRBRGRGBRGRGRGRBRBGRGBGR", "RGBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBGR", "RGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGR", "RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"};
	  vector <string> grid(grid_, grid_+sizeof(grid_)/sizeof(*grid_)); 
	int RetVal = 565039154;
	return verify_case(RetVal, ExtendableTriangles().getCount(grid)); }


template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE