本文共 5556 字，大约阅读时间需要 18 分钟。
题目大意：
一些点在一张无穷图上面，每个点可以控制一些区域，这个区域满足这个点到达这个区域的时间严格小于其他点。求哪些点能够控制无穷面积的区域。
题目思路：
速度小的控制范围一定有限。
速度最大当且仅当在凸包上才能够控制无穷区域。可以通过，任意两个点中垂线为界，左右各控制一半，判断出凸包内的点仅能控制有限区域。
特判：
速度最大且在同一个点上的点均不能控制无穷区域，但是要加入凸包计算。
速度最大为0不能控制无穷区域。
对于共线凸包（Graham），（代码中有解释）
均不能存在重点！可用map判重。
1、按极角坐标序排
缺点：需要将最后一条边上的点逆序排，才能够将最后一边共线点加入凸包。
2、按水平序排。
缺点：若所有点在一条直线上，会产生将所有点入凸包1~n~2的情况，需要特判，当然本题只是用到这些点，无需判断是否重复出现。
极角序：
#include #include #include #include #include #include #include #include #include #include #include #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) 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 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 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
水平序：
#include #include #include #include #include #include #include #include #include #include #include #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;int 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) 1 && sgn((vertex[Stack[top-1]]-vertex[Stack[top-2]])^(vertex[i]-vertex[Stack[top-2]])) < 0)//改为 <即可 top--; stack[top++]="i;" } int tmp="top;" for(int i> =0; i--) { while(top > tmp && sgn((vertex[Stack[top-1]]-vertex[Stack[top-2]])^(vertex[i]-vertex[Stack[top-2]])) < 0) top--; Stack[top++]=i; } if(n>1) top--;}int main(){ freopen("1002.in","r",stdin); freopen("1002p.out","w",stdout); map mapp; while(scanf("%d",&N)!=EOF && N) { memset(pd,-1,sizeof(pd)); n=0; maxv=-1; for(int i=1; i<=N; i++) { scanf("%d%d%d",&tx,&ty,&tv); if(maxv==tv && mapp[Point(tx,ty)]>0) { pd[mapp[Point(tx,ty)]]=0; pd[i]=0; continue; } if(maxv==tv) { vertex[n].x=tx; vertex[n].y=ty; vertex[n].re=i; mapp[vertex[n]]=i; n++; } if(maxv
水平序优化：（可以解决重点+共线凸包问题）
vis判水平序的点是否访问过，防止一条线的情况。
pd判是否重点，在水平排序后相邻的一定相邻！写的还算漂亮。毕竟map太暴力了。
#include #include #include #include #include #include #include #include #include #include #include #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define MAXN 505#define eps 1e-4using namespace std;struct Point{ double x,y; int res; Point(){} Point(double _x, double _y): x(_x),y(_y){} double operator^(Point A) { return x*A.y-A.x*y; } Point operator -(const Point A) const { return Point(x-A.x,y-A.y); }}vertex[MAXN];int Stack[MAXN],top;int N,n,x,y,v,Case;bool vis[MAXN],pd[MAXN];inline double dist(Point A){ return sqrt(A.x*A.x+A.y*A.y);}int sgn(double x){ if(fabs(x) 1 && (sgn(dist(vertex[Stack[top-1]]-vertex[Stack[top-2]]))==0 || sgn((vertex[Stack[top-1]]-vertex[Stack[top-2]])^(vertex[i]-vertex[Stack[top-1]]))<0)) vis[Stack[--top]]=0; Stack[top++]=i; vis[i]=1; } int tmp=top; for(int i=n-2; i>=0; i--) { while(top>tmp && (sgn(dist(vertex[Stack[top-1]]-vertex[Stack[top-2]]))==0 || sgn((vertex[Stack[top-1]]-vertex[Stack[top-2]])^(vertex[i]-vertex[Stack[top-1]]))<0)) vis[Stack[--top]]=0; if(!vis[i]) Stack[top++]=i; } //if(n>1) top--;}int main(){ while(scanf("%d",&N)!=EOF && N) { int maxv=-1; for(int i=0; i maxv) { maxv=v; n=0; } vertex[n].x=x; vertex[n].y=y; vertex[n].res=i; n++; } memset(vis,0,sizeof(vis)); memset(pd,1,sizeof(pd)); Graham(n); // for(int i=0; i 0) { for(int i=0; i
转载于:https://www.cnblogs.com/Mathics/p/3917693.html
