Bzoj3190: [jloi2013] racing car (monotone stack)

2020-12-07 15:31:28

solution ：
It's very similar to the horizontal visible line . It's just that this question is from y The ray at the beginning of the axis .
In fact, the train of thought is almost the same .

Monotone stack maintenance under convex hull .
First follow the straight line k Sort .
So when you come in t Other lines .

The current line is i. The line at the top of the stack is x.
If i and x The point of intersection is at y Shaft left .
So before the starting point x To surpass i.
So it's not legal , So the x Kick it out .

And then all that's left is the horizontal visible line .
The next element at the top of the stack is y.
If i and x The point of intersection is at x and y On the left side of the intersection . that x You're going to be kicked out, too
Draw a picture. Everything is clear .

At the end of the stack is the answer .

Code implementation ：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
struct node {

int k,b,id;}a;
int f,top;const double esp=1e-8;
double jd(node a,node b) {

return (double)(b.b-a.b)/(a.k-b.k);}
bool cmp(node n1,node n2) {

if(n1.k!=n2.k)return n1.k<n2.k;else return n1.b<n2.b;}
bool cmp1(int n1,int n2) {

return a[n1].id<a[n2].id;}int ans;
int main() {
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].b);
for(int i=1;i<=n;i++)scanf("%d",&a[i].k);
for(int i=1;i<=n;i++) a[i].id=i;
sort(a+1,a+1+n,cmp);top=0;
for(int i=1;i<=n;i++){
while(top>=1&&(a[i].b>a[f[top]].b ||
jd(a[i],a[f[top]])<jd(a[f[top]],a[f[top-1]]) ))top--;
f[++top]=i;
}
printf("%d\n",top);sort(f+1,f+1+top,cmp1);
printf("%d",a[f].id);
for(int i=2;i<=top;i++)printf(" %d",a[f[i]].id);
return 0;
}

https://chowdera.com/2020/12/20201207152119995y.html