【POJ 1113】 Wall
给n个点 连出一个凸包 然后在凸包外筑墙 要求墙与凸包每一处的距离都>=l 问需要建的最短的墙长
乍一看挺难 画画图就能看出来 凸包外建距离l的墙 其实就是在凸包每个顶点处 以顶点为圆心 做半径为l的弧 做到两侧半径与点的两边平行即可 然后把这些弧都用直线衔接 就是最短墙长
这样还不好求 呢把弧拿出来呢 其实就相当于把整个凸包作为一个点 以该点为圆心 l为半径做了个圆 这样弧的总长就是2*PI*l 那剩下的就是直线 平移下来其实就是凸包的周长
然后卷包裹法或者扫描法都能过 毕竟数据弱
代码如下:
//卷包裹法#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#define PI 3.141592653589793using namespace std;typedef struct Point{int x,y;double operator – (const struct Point a)const{return sqrt((x-a.x)*(x-a.x) + (y-a.y)*(y-a.y));}}Point;typedef struct Line{int x,y;bool operator > (const struct Line a)const//顺时针{return x*a.y – y*a.x > 0;}bool operator < (const struct Line a)const//逆时针{return x*a.y – y*a.x < 0;}}Line;Point pt[1000];int main(){int n,l,i;double len;int mp,tmp,mx;mp = 0;scanf("%d %d",&n,&l);for(i = 0; i < n; ++i)//输入 同时找到最左最下{scanf("%d %d",&pt[i].x,&pt[i].y);if(pt[i].x < pt[mp].x || (pt[i].x == pt[mp].x && pt[i].y < pt[mp].y))mp = i;}len = 2*PI*l;Line l1,l2;tmp = mp;//以最左最下的点为起点do//枚举每一个点 直到枚举完{mx = !tmp;for(i = 0; i < n; ++i){l1.x = pt[mx].x – pt[tmp].x;l1.y = pt[mx].y – pt[tmp].y;l2.x = pt[i].x – pt[tmp].x;l2.y = pt[i].y – pt[tmp].y;if(l2 > l1 || (!(l2 < l1) && pt[i]-pt[tmp] > pt[mx]-pt[tmp]))//找出极角最大并且距离前一点最远的点mx = i;}len += pt[mx]-pt[tmp];//每找出一个凸包上的点就加一条边tmp = mx;}while(tmp != mp);//找回原点时凸包就建好了printf("%.0f\n",len);return 0;}
//扫描法#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <stack>#include <algorithm>#define PI 3.141592653589793using namespace std;int xx,yy;typedef struct Point{int x,y;double operator – (const struct Point a)const{return sqrt((x-a.x)*(x-a.x) *1.0+ (y-a.y)*(y-a.y)*1.0);}bool operator < (const struct Point a)const{if(x == xx && y == yy) return false;if (a.x == xx && a.y == yy) return true;if((x-xx)*(a.y-yy) – (y-yy)*(a.x-xx) == 0) return sqrt((x-xx)*(x-xx) *1.0+ (y-yy)*(y-yy)*1.0) < sqrt((a.x-xx)*(a.x-xx) *1.0+ (a.y-yy)*(a.y-yy)*1.0);return (x-xx)*(a.y-yy) – (y-yy)*(a.x-xx) > 0;}}Point;typedef struct Line{int x,y;bool operator < (const struct Line a)const//逆时针{return x*a.y – y*a.x < 0;}}Line;Point pt[1000];stack <Point> s;void SetTb(int n)//建凸包{Line l1,l2;Point p1,p2;s.push(Point{xx,yy});s.push(pt[0]);for(int i = 1; i < n; ++i){p1 = s.top();s.pop();while(!s.empty()){p2 = s.top();s.pop();l1.x = pt[i].x – p2.x;l1.y = pt[i].y – p2.y;l2.x = p1.x – p2.x;l2.y = p1.y-p2.y;if(l1 < l2){s.push(p2);break;}p1 = p2;}s.push(p1);s.push(pt[i]);}}double Getlen()//从栈中不断出栈求凸包周长{Point p1,p2;double len = 0;p2 = s.top();s.pop();while(!s.empty()){p1 = s.top();s.pop();len += p2-p1;p2 = p1;}return len;}void Read(int &n,int &l)//输入并进行极角排序{int mp = 0;scanf("%d %d",&n,&l);for(int i = 0; i < n; ++i){scanf("%d %d",&pt[i].x,&pt[i].y);if(pt[i].x < pt[mp].x || (pt[i].x == pt[mp].x && pt[i].y < pt[mp].y))mp = i;}xx = pt[mp].x,yy = pt[mp].y;}int main(){int n,l,i;double len;Read(n,l);len = 2*PI*l;sort(pt,pt+n);SetTb(n);len += Getlen();printf("%.0f\n",len);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，积极的人在每一次忧患中都看到一个机会，
