kojingharangの日記

GCJ2012 Qualification D. Hall of Mirrors

10:55 |

• ２次元の世界に鏡があって自分が立ってるので自分がいくつ見えるかを求める問題。

• 難しそうなので部屋の壁にしか鏡がない small を考える
• 反射するイコール対称な位置に自分がいるということなので鏡の向こうの自分をたくさん配置する
• 各自分について、実際の自分の位置から見えるかどうか判定する。
• 距離が近いほうから見ていって、同一直線上にあったらカウントしない
• サンプルの 3x4 の部屋で 68 人も見える事にびっくり。実際のところは頭の幅とかあるからそんなに見えないかもしれないけど見てみたら怖そう...

• small 通ったけど large わからん。解説をみる

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int H,W,D;
		cin>>H>>W>>D;
		//cout<<H<<" "<<W<<" "<<D<<endl;
		
		int ox=0, oy=0;
		REP(h, H) {
			string s;
			cin>>s;
			REP(i, s.size()) if(s[i]=='X') {ox=i; oy=h;}
		}
		ox--;oy--;
		//cout<<ox<<" "<<oy<<endl;
		
		int ww = 100/(W-2)+1;
		int hh = 100/(H-2)+1;
		int ans = 0;
		vector<pair<int, PII> > l;
		for(int x=-ww;x<=ww;x++) {
			for(int y=-hh;y<=hh;y++) {
				int MX = x*(W-2)+(x%2==0 ? ox : W-2-ox-1)-ox;
				int MY = y*(H-2)+(y%2==0 ? oy : H-2-oy-1)-oy;
				int d = MX*MX+MY*MY;
				//if(d!=0 && d<=D*D) cout<<d<<"  "<<x<<" "<<y<<"    "<<MX<<" "<<MY<<endl;
				if(d!=0 && d<=D*D) l.PB(MP(d, MP(MX, MY)));
			}
		}
		//map<int, int> dh;
		
		sort(ALL(l));
		vector<PII> used;
		REP(i, l.size()) {
			int d = l[i].first;
			int MX=l[i].second.first;
			int MY=l[i].second.second;
			int ok=1;
			//cout<<"try "<<d<<" "<<MX<<" "<<MY<<endl;
			REP(j, used.size()) {
				int ux = used[j].first;
				int uy = used[j].second;
				if(MX*ux<0) continue;
				if(MY*uy<0) continue;
				if(ux==0) {
					if(MX!=0) continue;
					else {ok=0;break;}
				}
				if(uy==0) {
					if(MY!=0) continue;
					else {ok=0;break;}
				}
				int ug = GCD(ux, uy);
				int mg = GCD(MX, MY);
				if(ux/ug==MX/mg && uy/ug==MY/mg) {ok=0;break;}
			}
			if(ok) {
				//cout<<"X "<<d<<" "<<MX<<" "<<MY<<endl;
				//cout<<MX<<"\t"<<MY<<(MX==0 ? MY*10000000 : (double)MY/MX+(MX>0?1000:-1000))<<endl;
				//cout<<MX<<"\t"<<MY<<endl;
				ans++;
				used.PB(l[i].second);
				//dh[d]++;
			}
		}
		
		//vector<double> aa;
		//FOR(e, used) aa.PB(e->first==0 ? (double)e->second*1000000 : (double)e->second/e->first+(e->first>0?1000:-1000));
		//sort(ALL(aa));
		//REP(i, aa.size()-1) if(abs(aa[i]-aa[i+1]) < 0.00001) cout<<"ERROR"<<aa[i]<<" "<<aa[i+1]<<endl;
		//cout<<dh<<endl;
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

ツイートする