首页 > 代码库 > HDU 4946 凸包
HDU 4946 凸包
题目大意：
一些点在一张无穷图上面，每个点可以控制一些区域，这个区域满足这个点到达这个区域的时间严格小于其他点。求哪些点能够控制无穷面积的区域。
题目思路：
速度小的控制范围一定有限。
速度最大当且仅当在凸包上才能够控制无穷区域。可以通过，任意两个点中垂线为界，左右各控制一半，判断出凸包内的点仅能控制有限区域。
特判：
速度最大且在同一个点上的点均不能控制无穷区域，但是要加入凸包计算。
速度最大为0不能控制无穷区域。
对于共线凸包（Graham），
1、按极角坐标序排，需要将最后一条边上的点逆序排，才能够将最后一边共线点加入凸包。
2、按水平序排。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cmath>#include <vector>#include <utility>#include <stack>#include <queue>#include <map>#include <deque>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define INF 0x3f3f3f3fusing namespace std;const int MAXN = 1010;const double eps = 1e-8;const double PI = acos(-1.0);int tx,ty,tv,maxv,n,N,cas;bool pd[MAXN];int sgn(double x){ if(fabs(x) < eps) return 0; if(x < 0) return -1; return 1;}struct Point{ double x,y; int re; Point(){} Point(double _x, double _y): x(_x),y(_y) {} Point operator -(const Point &B) const { return Point(x-B.x, y-B.y); } Point operator +(const Point &B) const //向量相加 { return Point(x+B.x, y+B.y); } double operator ^(const Point &B) const //叉积 { return x*B.y - y*B.x; } double operator *(const Point &B) const //点积 { return x*B.x + y*B.y; } bool operator ==(const Point &B) const { return fabs(B.x-x)<eps && fabs(B.y-y)<eps; } bool operator !=(const Point &B) const { return !((*this) == B); } double norm()//向量的模 { return sqrt(x*x+y*y); } void transXY(double B) //绕原点逆时针旋转B弧度 { double tx = x, ty = y; x = tx*cos(B) - ty*sin(B); y = tx*sin(B) + ty*cos(B); } void input() //读入只能用double读入 { scanf("%lf%lf",&x,&y); }};struct Line{ Point s,e; Line(){} Line(Point _s, Point _e) { s=_s; e=_e; }};double dist(Point a, Point b){ return sqrt((a-b)*(a-b));}//判断点在线段上bool OnS(Point A, Line a){ return sgn((a.s-A)^(a.e-A)) == 0 && sgn((A.x-a.s.x)*(A.x-a.e.x)) <= 0 && sgn((A.y-a.s.y)*(A.y-a.e.y)) <= 0;}//求凸包 Graham算法//点的编号0~n-1//返回凸包结果Stack[0~top-1]为凸包的编号//一个点或两个点 则凸包为一或二个点int Stack[MAXN],top;Point vertex[MAXN];bool Graham_cmp(Point A, Point B){ double tmp=(A-vertex[0])^(B-vertex[0]); if(sgn(tmp) > 0) return 1; if(sgn(tmp) == 0 && sgn(dist(A,vertex[0])-dist(B,vertex[0])) <= 0) return 1; return 0;}void Graham(int n){ int k=0; for(int i=1; i<n; i++) if((vertex[k].y>vertex[i].y) || (vertex[k].y==vertex[i].y && vertex[k].x>vertex[i].x)) k=i; swap(vertex[0], vertex[k]); sort(vertex+1, vertex+n, Graham_cmp); if(n == 1) { top=1; Stack[0]=0; return; } if(n == 2) { top=2; Stack[0]=0; Stack[1]=1; return; } int tmp; for(tmp=n-1; tmp>1 && sgn((vertex[0]-vertex[tmp])^(vertex[0]-vertex[tmp-1])) == 0; tmp--); reverse(vertex+tmp,vertex+n);//最后一条边倒序 Stack[0]=0; Stack[1]=1; top=2; for(int i=2; i<n; i++) { while(top > 1 && (vertex[i] == vertex[Stack[top-1]] || sgn((vertex[Stack[top-1]]-vertex[Stack[top-2]])^(vertex[i]-vertex[Stack[top-2]])) < 0))//相同点只进栈一次 同一条线上的点也进栈 top--; Stack[top++]=i; }}int main(){ // freopen("1002.in","r",stdin); // freopen("1002p.out","w",stdout); while(scanf("%d",&N)!=EOF && N) { memset(pd,0,sizeof(pd)); n=0; maxv=-1; for(int i=0; i<N; i++) { scanf("%d%d%d",&tx,&ty,&tv); if(maxv==tv) { vertex[n].x=tx; vertex[n].y=ty; vertex[n].re=i; n++; } else if(maxv<tv) { maxv=tv; n=0; vertex[n].x=tx; vertex[n].y=ty; vertex[n].re=i; n++; } } Graham(n); for(int i=0; i<top; i++) pd[vertex[Stack[i]].re]=1; for(int i=0; i<n; i++)//去掉相同点 for(int j=i+1; j<n; j++) if(vertex[i]==vertex[j]) { pd[vertex[i].re]=0; pd[vertex[j].re]=0; } printf("Case #%d: ",++cas); for(int i=0; i<N; i++) { if(maxv==0) printf("0"); else printf("%d",pd[i]); } printf("\n"); } return 0;}/*0 0 10 10 11 12 13 11 1*/
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。