PKU演習問メモ(8/18)

No.	問題名	問題の種類および解法	難易度
1113	Wall	幾何・凸包	★★★★☆
2395	Out of Hay	クラスカル法	★★☆☆☆

1113 Wall

問題概要

座標平面上の多角形により表される城がある。
城のどの部分からも距離L以上離れ、城をすべて囲む塀を作りたい。
このような塀の最小の全長を求めよ。

城を表す多角形はその頂点を半時計周りに与えることによって指定される。
全ての座標は整数で、絶対値は10000以下である。
また。点の個数は1000を超えない。

解法

塀は全長が最短になるよう建設するため、凸包をとったものに、半径Lの円の周長を足したものが堀の全長になる。

解法が思い浮かばなかったので実プロwiki参照にした。そんなに簡単な問題ではないと思うのだけど……
まあ僕の頭が悪いだけだね。はい。

ソースコード

spaghetti sourceの凸包のコード（http://www.prefield.com/algorithm/geometry/convex_hull.html）を使用

int main()
{
	int n,l; scanf("%d%d",&n,&l);
	vector<P> poly;
	rep(i,n)
	{
		int x,y; scanf("%d%d",&x,&y);
		poly.pb(P(x,y));
	}
	poly=convex_hull(poly);
	n=poly.size();
	
	double ans=l*atan(1.0)*8;
	rep(i,n)ans+=abs(poly[i]-poly[(i+1)%n]);
	printf("%.0f\n",ans);
	
	return 0;
}

2395 Out of Hay

問題概要

N個の牧場がM本の双方向に通行可能な道でつながっている。
それぞれの道は両端の牧場と長さで与えられ、道が牧場以外で交差することはない。

全ての牧場を行き来したいが、通る最大の長さ道の長さを最小にしたい。このときの通る最大の道の長さを求めよ。

解法

クラスカル法をしながら最長辺の長さを覚えておけばよい。
頭まわってなくて添え字で2回もWA出した……

ソースコード

int n,m;
vector<pair<int,pi> >e;

int p[2000];
int root(int x)
{
	if(p[x]==x)return x;
	return p[x]=root(p[x]);
}
void merge(int a,int b)
{
	a=root(a); b=root(b);
	if(a!=b)p[a]=b;
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,m)
	{
		int a,b,c; scanf("%d%d%d",&a,&b,&c);
		e.pb(mp(c,mp(a-1,b-1)));
	}
	sort(all(e));
	
	rep(i,n)p[i]=i;
	int cnt=0,ans=0;
	fr(i,e)
	{
		int a=i->second.first,b=i->second.second;
		if(root(a)==root(b))continue;
		
		merge(a,b);
		ans=max(ans,i->first); cnt++;
		if(cnt==n-1)break;
	}
	printf("%d\n",ans);
	
	return 0;
}