cafelier@SRM

TCO09 Round2 600

あとで | 18:03 |

他の方の解法を参考に。

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;
  }
};

凸包かーなるほど。area計算の辺りがけっこうTLEギリギリだった。