TopCoder SRM 433 Div1 Medium SettingTents
問題
NxMの方眼紙がある(縦線がN+1本、横線がM+1本)
ここに、全ての頂点が方眼紙の交点であるようなひし形は何通り書くことができるか求めよ。
制約条件
N,M≦100
方針
ひし形をABCDとする。
辺AB,ADの候補のベクトルを全部生成する。
これは、(0,0)から(100,100)のベクトルを全部作ればよい。
ベクトルのうち、長さの等しいものをAB,ADとして二本選び、
実際にひし形を作ってみる。
ひし形の幅、高さをw,hとすると(ひし形をぴったり囲むような軸に平行な長方形の幅と高さ)、ひし形を方眼紙に書く場所は(N-w+1)*(M-h+1)通りあることがわかる。
これを全部の長さの等しいベクトルの組み合わせに対して見て、足し合わせてやればよい。
ソースコード
bool cmp(pi a,pi b){ double r1=hypot(a.first,a.second),r2=hypot(b.first,b.second); if(abs(r1-r2)>EPS)return r1<r2; return a<b; } class SettingTents { public: int countSites(int N, int M) { vector<pi> v; for(int i=0;i<=N;i++)for(int j=0;j<=M;j++)if(i||j){ v.pb(mp(i,j)); if(i&&j)v.pb(mp(i,-j)); } sort(all(v),cmp); int ans=0; rep(i,v.size()){ for(int j=i+1;j<v.size();j++){ double r1=hypot(v[i].first,v[i].second), r2=hypot(v[j].first,v[j].second); if(abs(r1-r2)>EPS)break; int tmp[]={v[i].second+v[j].second,v[i].second,v[j].second,0}; sort(tmp,tmp+4); int a=v[i].first+v[j].first,b=tmp[3]-tmp[0]; if(a<=N&&b<=M)ans+=(N-a+1)*(M-b+1); } } return ans; } };