首页 > 代码库 > UVa 1303 - Wall
UVa 1303 - Wall
题目:有很多点,修一座最短的围墙把素有点围起来,使得所有点到墙的距离不小于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; }
UVa 1303 - Wall
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。