题目:有非常多点。修一座最短的围墙把素有点围起来,使得全部点到墙的距离不小于 l。
分析:计算几何,凸包。
假设。没有距离 l 的限制。则答案就是凸包的周长了。有了距离限制事实上是添加了 2*π*l。
证明:如上图。在凸包外做相应边的矩形;
多边形内角和 = 180*(n-2);
外角和 = 360*n - 内角和 = 180*n+360;
全部直角和为 2*90*n;
所以,全部扇形的内角和为 360;即围栏比凸多边形周长多 2*π*l。
说明:坐标比較 a3.x <b.x 写成 a.x < b.y 查了好久才发现。o(╯□╰)o
- #include <algorithm>
- #include <iostream>
- #include <cstdlib>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- typedef struct pnode
- {
- int x,y;
- double d;
- }point;
- point P[1005];
- //叉乘
- int crossProduct(point a, point b, point c)
- {
- return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
- }
- //两点间距离
- double dist(point a, point b)
- {
- return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+0.0);
- }
- //坐标比較
- int cmp1(point a, point b)
- {
- if (a.x == b.x) return a.y < b.y;
- return a.x < b.x;
- }
- //斜率比較
- int cmp2(point a, point b)
- {
- int cp = crossProduct(P[0], a, b);
- if (!cp) return a.d < b.d;
- return cp > 0;
- }
- //凸包
- double Graham(int n)
- {
- sort(P+0, P+n, cmp1);
- for (int i = 1 ; i < n ; ++ i)
- P[i].d = dist(P[0], P[i]);
- sort(P+1, P+n, cmp2);
- int top = 1;
- for (int i = 2 ; i < n ; ++ i) {
- while (top > 0 && crossProduct( P[top-1], P[top], P[i] ) < 0) -- top;
- P[++ top] = P[i];
- }
- P[++ top] = P[0];
- double L = 0.0;
- for ( int i = 0 ; i < top ; ++ i )
- L += dist(P[i], P[i+1]);
- return L;
- }
- int main()
- {
- int t,n,l;
- while (~scanf("%d",&t))
- while (t --) {
- scanf("%d%d",&n,&l);
- for (int i = 0 ; i < n ; ++ i)
- scanf("%d%d",&P[i].x,&P[i].y);
- printf("%.0lf\n",Graham(n)+acos(-1.0)*2*l);
- if (t) printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2032034.html