标签:计算几何
Description
在xoy直角坐标平面上有n条直线L1,L2,...Ln,若在y值为正无穷大处往下看,能见到Li的某个子线段,则称Li为
可见的,否则Li为被覆盖的.
例如,对于直线:
L1:y=x; L2:y=-x; L3:y=0
则L1和L2是可见的,L3是被覆盖的.
给出n条直线,表示成y=Ax+B的形式(|A|,|B|<=500000),且n条直线两两不重合.求出所有可见的直线.
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号,两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Input
3
-1 0
1 0
0 0
Sample Output
1 2
分析:可以将本题的函数画图像,实质上就是维护一个类似于上凸包,按照斜率a排序,如果其与栈顶元素的交点在其左边,那么就将在这个函数出栈,否则最后栈内的函数就是答案
Code
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define LL long long #define mem(x,num) memset(x,num,sizeof x) #define eps 1e-8 using namespace std; const int maxn=5e4+6; struct node{double x,y;int id;}a[maxn],st[maxn]; int top,n; bool ans[maxn]; inline bool cmp(node a,node b){return fabs(a.x-b.x)<eps ? a.y<b.y : a.x<b.x;} double crossx(node a,node b){return (b.y-a.y)/(a.x-b.x);} void ins(node a) { while(top){ if(fabs(st[top].x-a.x)<eps)top--; else if(top>1&&crossx(a,st[top-1])<=crossx(st[top],st[top-1]))top--; else break; } st[++top]=a; } int main() { scanf("%d",&n); rep(i,1,n)scanf("%lf%lf",&a[i].x,&a[i].y),a[i].id=i; sort(a+1,a+1+n,cmp); rep(i,1,n)ins(a[i]); rep(i,1,top)ans[st[i].id]=1; rep(i,1,n) if(ans[i])printf("%d ",i); return 0; }