[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;