naoya_t@topcoder

SRM433 Div1 Medium: SettingTents

過去問, 練習 | 00:14 |

• 幅w=1〜N、高さh=1〜Mの長方形を考え、その中にぴったり収まる菱形の個数を得る関数count(w,h)を考えれば

• ４頂点が辺の上にあるとは限らない。本戦ではそれで失敗
• 同じ菱形を重複して数えていたりして悩んだ
• 時間あるのでatan使って角度でソートとかしちゃう

#define sz(a)  int((a).size())
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define all(c)  (c).begin(),(c).end()
#define evenp(x) (((x)&1)==0)
#define oddp(x) (((x)&1)==1)

class SettingTents {
  int count(int w, int h){
    double cx=0.5*w, cy=0.5*h;
    int c=0;
    int x0=0,x2=w;
    set<pair<pair<int,int>,pair<int,int> > > cnt;
    for(int y0=0;y0<=h;y0++){
      int y2=h-y0;
      if(y2==y0) continue;
      for(int x1=0;x1<=w;x1++){
        int x3=w-x1;
        if(x1==x3) continue;
        int rhs=w*(2*x1-w);
        int l=2*y0-h;
        if(abs(rhs)%abs(l)) continue;
        int yy=rhs/l+h; // 2y
        if(oddp(yy)) continue;
        int y1=yy/2, y3=h-y1;
        if(y1<0 || h<y1) continue;
        if(y0*y1*y2*y3>0) continue;
        if(x0==x1 && y0==y1) continue;
        if(x2==x1 && y2==y1) continue;
        if(x3==x1 && y3==y1) continue;
        vector<pair<double,pair<int,int> > > v(4);
        v[0] = make_pair(atan2(-cy+y0,-cx+x0), make_pair(x0,y0));
        v[1] = make_pair(atan2(-cy+y1,-cx+x1), make_pair(x1,y1));
        v[2] = make_pair(atan2(-cy+y2,-cx+x2), make_pair(x2,y2));
        v[3] = make_pair(atan2(-cy+y3,-cx+x3), make_pair(x3,y3));
        sort(all(v));
        cnt.insert(make_pair(v[0].second, v[1].second));
      }
    }
    c = cnt.size();
    if(evenp(w) && evenp(h)) c++;
    return c;
  }
 public:
  int countSites(int N, int M) {
    int c=0;
    for(int w=1;w<=N;w++)
      for(int h=1;h<=M;h++)
        c+=(N-w+1)*(M-h+1)*count(w,h);
    return c;
  }
};