TCO '09 Round2 Medium ExtendableTriangles

問題概要

nxm個の長方形に並んだ格子点があり、
点のそれぞれの色が'R','G','B'のいずれかである。

異なる3点を結んでできる三角形（三点が同一直線上にあってもよい）のうち、
3点の色が異なる三角形を「美しい」三角形と呼ぶ。

美しい三角形のうち、「二辺を共有する美しい三角形で、面積が真により大きなものがある」三角形は「拡大可能」であるという。

拡大可能な三角形の数を求めよ。

制約条件

n,m≦50

方針

美しい三角形の総数は('R'の点の数)x('G'の点の数)x('B'の点の数)になる。
そこから拡大可能でない美しい三角形（以下極大三角形）の数を引けばよい。

極大三角形の数を、愚直に求めようとすると
三角形を全列挙しなければならないのでO(2500^3/6)の時間がかかってTLE.

極大三角形の各頂点は、色ごとに列または行の両端になることに注目する。
すると頂点の候補が200x200x200に減り全探索できる。

ソースコード

int A(pi a,pi b,pi c){
	int x=b.first-a.first,X=c.first-a.first;
	int y=b.second-a.second,Y=c.second-a.second;
	return abs(x*Y-y*X);
}
int area[200][200][200];
int maxRG[200][200],maxGB[200][200],maxRB[200][200];

class ExtendableTriangles {
public:
  int getCount(vector <string> grid) {
  	int h=grid.size(),w=grid[0].size();
  	int cnt[3]={}, tonum[256];
  	
  	tonum['R']=0; tonum['G']=1; tonum['B']=2;
  	vector<pi> P[3];
  	
  	rep(i,h)rep(j,w){
  		int c=tonum[grid[i][j]];
  		cnt[c]++;
  		
  		int y=i-1,Y=i+1,x=j-1,X=j+1;
  		for(;y>=0&&grid[y][j]!=grid[i][j];)y--;
  		for(;x>=0&&grid[i][x]!=grid[i][j];)x--;
  		for(;Y<h&&grid[Y][j]!=grid[i][j];)Y++;
  		for(;X<w&&grid[i][X]!=grid[i][j];)X++;
  		
  		if(y<0||Y>=h||x<0||X>=w)P[c].pb(mp(i,j));
  	}
  	rep(i,3){
  		sort(all(P[i]));
  		P[i].erase(unique(all(P[i])),P[i].end());
  	}
  	
  	rep(i,200)rep(j,200)maxRG[i][j]=maxRB[i][j]=maxGB[i][j]=0;
  	
  	rep(r,P[0].size())rep(g,P[1].size())rep(b,P[2].size()){
  		area[r][g][b]=A(P[0][r],P[1][g],P[2][b]);
  		maxRG[r][g]=max(maxRG[r][g],area[r][g][b]);
  		maxRB[r][b]=max(maxRB[r][b],area[r][g][b]);
  		maxGB[g][b]=max(maxGB[g][b],area[r][g][b]);
  	}
  	
  	ll ans=(ll)cnt[0]*cnt[1]*cnt[2];
  	rep(r,P[0].size())rep(g,P[1].size())rep(b,P[2].size())
  	if(maxRG[r][g]==area[r][g][b]&&
  		maxGB[g][b]==area[r][g][b]&&
  		maxRB[r][b]==area[r][g][b])ans--;
  	
    return ans;
  }
};