卧薪尝胆,厚积薄发。
JLOI2013 赛车
Date: Sun Dec 09 15:57:58 CST 2018 In Category: NoCategory

Description:

给你很多赛车,每个赛车有速度和起始位置,问有哪些赛车曾经领跑过。
$1\leqslant n\leqslant 10^4$

Solution:

和[HNOI2008\]水平可见直线类似的做法,但是由于不保证斜率不同,所以要把斜率相同的合并。

Code:


#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cctype>
#include<cstring>
using namespace std;
int n;
#define MAXN 50010
struct line
{
double k,b;
vector<int> id;
}l_[MAXN],l[MAXN];
bool cmp_k(line a,line b){return a.k < b.k;}
line stack[MAXN];
int top = 0;
struct point
{
double x,y;
};
point intersection(line x,line y)
{
point res;
res.x = (x.b - y.b) / (y.k - x.k);
res.y = res.x * x.k + x.b;
return res;
}
bool under(point k,line l)
{
return (k.x * l.k + l.b > k.y);
}
int ans[MAXN];
bool equal(double a,double b){return fabs(a - b) <= 1e-10;}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;++i)scanf("%lf",&l_[i].b);
for(int i = 1;i <= n;++i)scanf("%lf",&l_[i].k);
for(int i = 1;i <= n;++i)l_[i].id.push_back(i);
sort(l_ + 1,l_ + 1 + n,cmp_k);
int cnt = 0;
for(int i = 1;i <= n;++i)
{
if(cnt == 0)l[++cnt] = l_[i];
else if(!equal(l[cnt].k,l_[i].k))l[++cnt] = l_[i];
else if(equal(l_[i].b,l[cnt].b))l[cnt].id.push_back(l_[i].id[0]);
else if(l_[i].b > l[cnt].b)l[cnt] = l_[i];
}
n = cnt;
for(int i = 1;i <= n;++i)
{
while(top >= 2 && under(intersection(stack[top],stack[top - 1]),l[i]))--top;
stack[++top] = l[i];
}
int tot = 0;
for(int i = 1;i <= top;++i)
{
if(i < top && intersection(stack[i],stack[i + 1]).x < 0)continue;
for(int j = 0;j < stack[i].id.size();++j)ans[++tot] = stack[i].id[j];
}
sort(ans + 1,ans + 1 + tot);
cout << tot << endl;
for(int i = 1;i <= tot;++i)printf("%d ",ans[i]);cout << endl;
return 0;
}
Copyright © 2020 wjh15101051
ღゝ◡╹)ノ♡