PKU 1113 Wall .

Wall

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 18398		Accepted: 5992

Description

Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King's castle. The King was so greedy, that he would not listen to his Architect's proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall. 

         
Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King's requirements.

The task is somewhat simplified by the fact, that the King's castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle's vertices in feet.

Input

The first line of the input file contains two integer numbers N and L separated by a space. N (3 <= N <= 1000) is the number of vertices in the King's castle, and L (1 <= L <= 1000) is the minimal number of feet that King allows for the wall to come close to the castle.

Next N lines describe coordinates of castle's vertices in a clockwise order. Each line contains two integer numbers Xi and Yi separated by a space (-10000 <= Xi, Yi <= 10000) that represent the coordinates of ith vertex. All vertices are different and the sides of the castle do not intersect anywhere except for vertices.

Output

Write to the output file the single number that represents the minimal possible length of the wall in feet that could be built around the castle to satisfy King's requirements. You must present the integer number of feet to the King, because the floating numbers are not invented yet. However, you must round the result in such a way, that it is accurate to 8 inches (1 foot is equal to 12 inches), since the King will not tolerate larger error in the estimates.

Sample Input

9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200

Sample Output

1628

Hint

结果四舍五入就可以了

Source

Northeastern Europe 2001

 

琴日我地EK1412分享左滴题目，其中101majia就分比我地呢个凸包入门题目。

 

之后今日早上用左个几钟睇完导论里面几何部分，发觉自己以前果中高中计算方法真系落后鸟{=      =}。

用高数里面既叉积实在可以做到好多野，而且精度高，判断又快，基本可以称得上系几何算法既核心。

关于叉积(CrossProduct)

大家可以系高数或者其他几何书度睇到，呢度就吾再9up。

 

今日既重点系GrahamScan。

首先介绍极角排序(PolarAngleSort)

个名好有型，但系其实好简单。

 

首先讲一下咩叫极角(PolarAngle)：

举个例子，假设我地以坐标点O(1, 1)为极点，有一个点P(2, 2)，P - O = (1, 1)，则系该极点既极坐标系里面，P点“极角”就为

45度。

 

 跟住到极角排序：

我地取y坐标最小既点(y坐标相同时取x较小者)作为极点，然后从次小极开始逆时针扫描，同一极角取与极点距离较远者

较近者"舍去"，按扫描到既次序得到既点序列就系极角排序之后既序列。

 

之后系GrahamScan算法：

 

算法首先将排序后点集前三个点压入堆栈，然后顺序扫描，判断用栈顶同埋次栈顶元素同，待测点点组成既折线用叉积判定该点

转向，如果转右，就弹出栈顶元素，继续判断直到待测点转左，之后将待测点压入栈顶，证明正确性好长，参考算法导论{=       =}。

 

翻译一下导论里面既伪代码：

GRAGAM_SCAN(Q)                      //Q为原始点集

1 对Q进行极角排序

2 PUSH(p0,S)                               

3 PUSH(p1,S)

4 PUSH(p2,S)                                //S为栈，初始化压入排序后Q前三个点

5 for i <- 3 to m do

7     while 以栈顶，次栈顶及pi组成既角是否右转

           do  POP(S)

8 PUSH(pi, S)

10 return S                                     //最后S即为凸集，顺序为逆时针

 

分析题目：

 

其实就系稳一个凸包，然后放大。

我初先WA问题出系两度：

第一、我将放大捻复杂左，造成精度大缺失，其实就系加上一个半径为L既圆。

第二、无留意一个地方，就系"同一极角取与极点距离较远者较近者舍去"，其实根据算法特性，吾一定要舍去(只需要系上面伪代码while

判断中加入判断平行)，但系我地要考虑一个特殊情况，就系初始化时候，如果无舍弃，第三个点p2就有可能系与p0p1共线并且无条件

压入S，造成最后统计周长时候多出一段多余既p1p2。所以我选取p2时候加入平行判断，AC。

 

下面贴代码:

8966829

GZHU1006100106

1113

Accepted

232K

32MS

C++

2094B

2011-07-22 15:46:02

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXI 1011
#define sq(x) ((x) * (x)) //Square

struct pt { double x, y; } ps[MAXI];
vector<pt> st;          //Pseudo-Stack {=  =}
int n, len;
double l;

double dlt(pt &a, pt &b, pt &o) //Cross-Product
{
	return (o.x - a.x) * (b.y - a.y) - (b.x - a.x) * (o.y - a.y);
}

double dis(pt &a, pt &b) //Distance
{
	return sqrt(sq(a.x - b.x) + sq(a.y - b.y));
}

bool pac(pt &a, pt &b) //Polar-Angle-Compare
{
	double delta = dlt(a, b, ps[0]);

	if ( delta == 0 && sq(a.x - ps[0].x) + sq(a.y - ps[0].y) > sq(b.x - ps[0].x) + sq(b.y - ps[0].y))
		return 1;
	else if (delta < 0)
		return 1;
	return 0;
}

void pas() //Polar-Angle-Sort
{
	int i, id;

	for (id = 0, i = 1; i < n; i++)
		if ((ps[i].y == ps[id].y && ps[i].x < ps[id].x) ||
			 ps[i].y < ps[id].y)
			id = i;
	swap(ps[0], ps[id]);
	sort(ps + 1, ps + n, pac);
#if 0
		for (i = 0; i < n; i++)
			printf("p%d = [%lf, %lf]\n", i, ps[i].x, ps[i].y);
#endif
}

void ghs() //Graham's-Scan
{
	int i;

	pas();
	len = 2;
	st.clear();
	st.push_back(ps[0]);
	st.push_back(ps[1]);
	for (i = 2; i < n; i++)
		if (dlt(st[1], ps[i], st[0]) != 0)
			break;
	st.push_back(ps[2]);
	for (i++; i < n; i++)
	{
		while (dlt(st[len], ps[i], st[len - 1]) >= 0)
		{
			st.pop_back();
			len--;
		}
		st.push_back(ps[i]);
		len++;
	}
	len++;
#if 0
		for (i = 0; i < len; i++)
			printf("p%d = [%lf, %lf]\n", i, st[i].x, st[i].y);
#endif
}

double sta() //Statistic
{
	int i;
	double tsu = 0.0;

	for (i = 0; i < len; i++)
		tsu += dis(st[i % len], st[(i + 1) % len]);
		
#if 0
	printf("%lf\n", dlt(st[1], st[2], st[0]) / (dis(st[0], st[1]) * dis(st[1], st[2])));
#endif

	return tsu + 4.0 * asin(1.0) * l;
}

int main()
{
	int i;
#if 0
	printf("%lf\n", 4.0 * asin(1.0) * 100);
#endif
	while (scanf("%d%lf", &n, &l) != EOF)
	{
		for (i = 0; i < n; i++)
			scanf("%lf%lf", &ps[i].x, &ps[i].y);
		ghs();
		printf("%d\n", (int)(sta() + 0.5));
	}

	return 0;
}

 

第一次用代码控件…………

今日学到好多几何野，想写好多野，以后再写写吧，关于几何既野{=__.=+}

大家都可以去101majia既关于PKU1113题目文章果度参考下噶！

地址呢度http://gzhu-101majia.iteye.com/blog/1128755