kmjp's blog

競技プログラミング参加記です

TopCoder SRM 739 Div1 Hard MakePolygon

本番方針はあってたので時間内に解ききりたかった…。
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を超える場合、そこから右側にギザギザを伸ばそう。
真ん中はほぼ全格子点を利用するので、割と余裕がある。
f:id:kmjp:20181013115600p:plain

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

まとめ

単独全完のチャンスが…。