本番方針はあってたので時間内に解ききりたかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=15097
問題
正整数Nが与えられる。
2次元座標上(1,1)-(25,25)の矩形区間の格子点を結んでできるシンプルなN角形のうち、面積最小のものを構築せよ。
解法
ピックの定理を考えると、
- 多角形内部に格子点がない
- 多角形の辺は頂点部以外に格子点を通らない
ようにすると面積N/2-1が最小値とわかる。
上記を実現するように多角形を構築しよう。
使える格子点の位置は625箇所で、Nは最大500なのでかなり密度濃く敷き詰める必要がある。
解を書いてしまうと以下の通り。
Nが50以下なら、左端に縦のギザギザを構築すればよい。
50を超える場合、そこから右側にギザギザを伸ばそう。
真ん中はほぼ全格子点を利用するので、割と余裕がある。
class MakePolygon { public: int area(vector<pair<int,int>> P) { int ret=0; int i; P.push_back(P[0]); FOR(i,P.size()-1) { ret+=P[i].first*P[i+1].second-P[i+1].first*P[i].second; } ret=abs(ret); return ret; } int pat[51][51]; vector <int> make(int N) { vector<pair<int,int>> P; int x,y; cin>>N; int ON=N; if(N<=50) { deque<pair<int,int>> D; for(int y=1;D.size()<min(50,N);y++) { D.push_front({2-y%2,y}); if(D.size()<N) D.push_back({3-y%2,y}); } FORR(d,D) P.push_back(d); } else { N-=50; P.push_back({3,1}); for(y=2;y<=22;y+=2) { P.push_back({2,y}); vector<pair<int,int>> A,B; deque<pair<int,int>> D; for(x=3;x<=25;x++) { if(x==3) { if(N) A.push_back({x,y}), N--; } else { if(N) A.push_back({x,y+(1-x%2)}), N--; if(N) B.push_back({x,y+1+(1-x%2)}), N--; } } FORR(a,A) P.push_back(a); reverse(ALL(B)); FORR(b,B) P.push_back(b); while(D.size()) P.push_back(D.front()), D.pop_front(); P.push_back({3,y+1}); } P.push_back({2,24}); P.push_back({3,25}); for(y=25;y>=1;y--) P.push_back({1+y%2,y}); } FORR(p,P) cout<<p.first<<" "<<p.second<<endl; cout<<area(P)<<endl; assert(area(P)+2==ON); vector<int> Q; FORR(p,P) Q.push_back(p.first*100+p.second); return Q; } }
まとめ
単独全完のチャンスが…。