「BZOJ1007」[HNOI2008] 水平可见直线
Description
Input
第一行为N(0 < N < 50000),接下来的N行输入Ai,Bi
Output
从小到大输出可见直线的编号，两两中间用空格隔开,最后一个数字后面也必须有个空格
Sample Input
3
-1 0
1 0
0 0
-1 0
1 0
0 0
Sample Output
1 2
题解
算法比较直观，先按斜率排序，再将最小的两条线入栈，然后依次处理每条线，如果其与栈顶元素的交点在上一个点的左边，则将栈顶元素出栈 ；这样为什么对呢？因为对如任意一个开口向上的半凸包，从左到右依次观察每条边和每个顶点，发现其斜率不断增大，顶点的横坐标也不断增大。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #define eps 1e-8 using namespace std; struct data{double a,b;int n;}l[50001]; data st[50001];bool ans[50001]; int top,n; inline bool cmp(data a,data b) { if(fabs(a.a-b.a)<eps)return a.b<b.b; else return a.a<b.a; } double crossx(data x1,data x2) {return (x2.b-x1.b)/(x1.a-x2.a);} void insert(data a) { while(top) { if(fabs(st[top].a-a.a)<eps)top--; else if(top>1&&crossx(a,st[top-1])<=crossx(st[top],st[top-1])) top--; else break; } st[++top]=a; } void work() { for(int i=1;i<=n;i++)insert(l[i]); for(int i=1;i<=top;i++)ans[st[i].n]=1; for(int i=1;i<=n;i++) if(ans[i])printf("%d ",i); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf%lf",&l[i].a,&l[i].b); l[i].n=i; } sort(l+1,l+n+1,cmp); work(); return 0; } |
计数器 9854191
OI 课件=>
OI 课件=>
为什么crossx(a,st[top-1])<=crossx(st[top],st[top-1])可以判断交点在左边？
crossx求出两直线方程关于x的解.. 根据x坐标的大小就可以判断左右呀.
擦,有人冒充我
黄学长刷的题好多。。但学长表示800道题足够进队了
以前学长和我说bzoj100题就能进队。。。这是命吧