1272-Polygons on the Grid

問題概要

辺の流さが与えられた数値で表わせる，頂点が格子点上にある凸型多角形の面積の最大を求めよ．

解法

枝刈り全探索.
辺の使い方(1 2 4 5を3 4 5や5 5 2にするなど)をまず全探索する．
それぞれの辺の使い方に対し，辺の並び方をnext_permutationなどで決める．
凸にならないようなものや，遠すぎるようなものを枝刈りして，最大の面積を求める．

実装(C++)

#include <iostream>
#include <complex>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
#include <ctime>
#include <cstdio>
#include <set>
using namespace std;

const double EPS=1e-7;
const double INF=1e10;
#define REP(i,x) for(int i=0;i<(int)x;i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
typedef complex<int> Point;
ostream &operator<<(ostream &os,const Point &a){
	return os<<"("<<real(a)<<","<<imag(a)<<")";
}
inline int cross(const Point &a,const Point &b){return imag(conj(a)*b);}
inline int dot(const Point &a,const Point &b){return real(conj(a)*b);}
namespace std{
bool operator<(const Point &a,const Point &b){return real(a)==real(b)?imag(a)<imag(b):real(a)<real(b);}
Point operator*(const Point &a,const double &b){return Point(real(a)*b,imag(a)*b);}
}
int ccw(Point a,Point b,Point c){
	b-=a;c-=a;
	if(cross(b, c)>0)return +1;       // counter clockwise
	if(norm(b)<norm(c))return -2;       // a--b--c on line
	return 0;
}
#define curr(P, i) P[(i) % n]
#define next(P, i) P[(i+1) % n]
#define prev(P, i) P[(i+n-1) % n]

typedef pair<int,int> Q;
vector<Point> circle[1801];

int n;
int r[6];
Point P[6];
int Sum;
int area(int m){
	int A=0;
	for(int i=0;i<m;++i)
		A+=cross(curr(P, i),next(P, i));
	return A/2;
}
int debug=0;
int answer=-1;
void solve(int k){
	if(k>1)Sum-=r[k-2];
	debug++;
	if(k>2){
		int t=ccw(P[k-3],P[k-2],P[k-1]);
		if(t!=1){
			if(k>1)Sum+=r[k-2];
			return;
		}
	}
	if(k>1&&P[k-1].real()==0&&P[k-1].imag()==0){
		if(k>1)Sum+=r[k-2];
		return;
	}
	if(P[k-1].imag()<0){
		if(k>1)Sum+=r[k-2];
		return;
	}
	if(norm(P[k-1]-P[0])>Sum*Sum){
		if(k>1)Sum+=r[k-2];
		return;
	}
	if(k==n){
		//解があるかどうか
		for(int i=0;i<(int)circle[r[k-1]].size();i++){
			if(abs(P[k-1].real())==abs(circle[r[k-1]][i].real())&&abs(P[k-1].imag())==abs(circle[r[k-1]][i].imag())){
				answer=max(answer,area(n));
				break;
			}
		}
	}else if(k==1){
		//辺を適当に置く(45度の範囲)
		for(int i=0;i<(int)circle[r[k-1]].size()/2;i++){
			P[k]=circle[r[k-1]][i];
			solve(k+1);
		}
	}else{
		//辺を適当に置く
		for(int i=0;i<(int)circle[r[k-1]].size();i++){
			P[k].real()=circle[r[k-1]][i].real()+P[k-1].real();
			P[k].imag()=circle[r[k-1]][i].imag()+P[k-1].imag();
			solve(k+1);

			P[k].real()=-circle[r[k-1]][i].real()+P[k-1].real();
			P[k].imag()=circle[r[k-1]][i].imag()+P[k-1].imag();
			if(circle[r[k-1]][i].real())solve(k+1);

			P[k].real()=circle[r[k-1]][i].real()+P[k-1].real();
			P[k].imag()=-circle[r[k-1]][i].imag()+P[k-1].imag();
			if(circle[r[k-1]][i].imag())solve(k+1);

			P[k].real()=-circle[r[k-1]][i].real()+P[k-1].real();
			P[k].imag()=-circle[r[k-1]][i].imag()+P[k-1].imag();
			solve(k+1);

			P[k]=P[0];
		}
	}
	if(k>1)Sum+=r[k-2];
	return;
}

void solve(){
	int min_c=0;
	sort(r,r+n,greater<int>());
	REP(i,n){
		if(circle[r[min_c]].size()>circle[r[i]].size()){
			min_c=i;
		}
	}
	swap(r[0],r[min_c]);
	sort(r+1,r+n,greater<int>());
	Sum=accumulate(r,r+n,0);
	do{
		P[0]=Point(0,0);
		debug=0;
		solve(1);
	}while(next_permutation(r+1,r+n,greater<int>()));
}
set<multiset<int> > ac;
void dfs(multiset<int> r_data){
	if(r_data.size()<3)return;
	if(ac.find(r_data)==ac.end()){
		ac.insert(r_data);
		n=r_data.size();
		int k=0;
		int t[6];
		FOR(it,r_data){
			t[k]=*it;
			r[k++]=*it;
		}
		n=k;
		solve();
		for(int i=0;i<r_data.size();i++){
			for(int j=i+1;j<r_data.size();j++){
				multiset<int> next;
				next.insert(t[i]+t[j]);
				for(int k=0;k<r_data.size();k++){
					if(k==i||k==j)continue;
					next.insert(t[k]);
				}
				dfs(next);
			}
		}
	}
}
int main() {
	for(int i=1;i<=1800;i++){
		for(int j=0;j<=i;j++){
			int t=sqrt(i*i-j*j)+1e-8;
			if(t*t+j*j==i*i){
				circle[i].push_back(Point(t,j));
			}
		}
	}
	for(;cin>>n,n;){
		REP(i,n)cin>>r[i];
		answer=-1;
		ac.clear();
		multiset<int> v;
		REP(i,n)v.insert(r[i]);
		dfs(v);
		cout<<answer<<endl;
	}
	return 0;
}