当前位置:网站首页>Bzoj3190: [jloi2013] racing car (monotone stack)

Bzoj3190: [jloi2013] racing car (monotone stack)

2020-12-07 15:31:28 osc_ z9t307rr

Subject portal
.

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[51000];
int f[51000],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[11000];
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[1]].id);
    for(int i=2;i<=top;i++)printf(" %d",a[f[i]].id);
    return 0;
}

版权声明
本文为[osc_ z9t307rr]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201207152119995y.html