[BZOJ3190][JLOI2013]赛车（计算几何+单调栈）

2019-11-08 18:29:38

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题解

一辆赛车行驶的路程就是v*t+k 看成一条条直线就是水平可见直线那道题了… 按照斜率排序之后用单调栈维护，每一次计算交点然后判断是否覆盖就行了最后栈中且和下一条直线交点的横坐标>=0的直线是合法的

坑点：判断平行直线，选b最大的判断重合直线，栈中只能保留一条，最后输出的时候将所有的全部输出（不能直接在维护的时候打标记，因为有可能在以后弹出）题面说得很清楚，只要没有超过它的就行，所以重合的点也是满足的

也可以用nlogn半平面交似乎

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 10005const double eps=1e-12;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}struct Line{ int id,num; double k,b; bool Operator < (const Line &a) const { return k<a.k||a.k==k&&b>a.b; }};int n,top,ans[N];Line l[N],stack[N];bool flag[N];double X(Line p,Line q){ return (q.b-p.b)/(p.k-q.k);}double Y(Line l,double x){ return x*l.k+l.b;}bool check(Line p,Line q,Line r){ double x=X(p,q); double py=Y(p,x); double ry=Y(r,x); return dcmp(py-ry)<0;}int main(){ scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%lf",&l[i].b),l[i].id=i; for (int i=1;i<=n;++i) scanf("%lf",&l[i].k); sort(l+1,l+n+1); for (int i=1;i<=n;++i) l[i].num=i; for (int i=1;i<=n;++i) { if (top&&dcmp(l[i].k-stack[top].k)==0) continue; while (top>1&&check(stack[top],stack[top-1],l[i])) --top; stack[++top]=l[i]; } for (int i=1;i<=top;++i) { if (i!=top) { double x=X(stack[i],stack[i+1]); if (dcmp(x)<0) continue; } Line now=stack[i]; for (int i=now.num;i<=n;++i) if (dcmp(now.k-l[i].k)==0&&dcmp(now.b-l[i].b)==0) flag[l[i].id]=1; else break; } for (int i=1;i<=n;++i) if (flag[i]) ++ans[++ans[0]]=i; PRintf("%d/n",ans[0]); for (int i=1;i<=ans[0];++i) printf("%d%c",ans[i]," /n"[i==ans[0]]);}

上一篇：System.InvalidOperationException: 此实现不是 Windows 平台 FIPS 验证的加密算法的一部分。

下一篇：POJ3185-The Water Bowls-反转问题

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注