刷题总结——赛车（bzoj3190）

题目：

题目背景

JLOI2013 T1

题目描述

这里有一辆赛车比赛正在进行，赛场上一共有 N 辆车，分别称为 g1，g2，……，gn。赛道是一条无限长的直线。最初，gi 位于距离起跑线前进 ki 的位置。比赛开始后，车辆 gi 将会以 vi 单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务就是算出那些赛车将会得奖。

输入格式

第一行有一个正整数 N 表示赛车的个数。
接下来一行给出 N 个整数，按顺序给出 N 辆赛车的起始位置。
再接下来一行给出 N 个整数，按顺序给出 N 辆赛车的恒定速度。

输出格式

输出包括两行，第一行为获奖的赛车个数。
第二行按从小到大的顺序输出获奖赛车的编号，编号之间用空格隔开，注意最后一个编号后面不要加空格。

样例数据 1

输入　 [复制]

 

4 
1 1 0 0 
15 16 10 20

输出

3 
1 2 4

备注

【数据范围】
对于 20% 的数据：N<=10
对于 50% 的数据：N<=6000
对于 100% 的数据：N<=10000, 0<=ki<=109, 0<=vi<=109

题解：

　　半平面交模版的，注意在两端点不确定的情况下充分利用斜率和交点，另外

心得：

　　模版题模版题啦啦啦

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const double minn=1e-8;
const int N=100005;
int read()
{
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct line
{
  int pos;
  int v;
  int id;
}car[N],q[N],a[N];
int cnt,ans[N];
double interx(line a,line b)
{
  return (double)(b.pos-a.pos)/(a.v-b.v);
}
bool comp(line a,line b)
{
  if(a.v!=b.v)  return a.v<b.v;
  else return a.pos<b.pos;
}
bool jud(line a,line b,line c)
{
  return interx(a,b)>interx(a,c);
}
int main()
{
 // freopen("a.in","r",stdin);
  cnt=read();
  for(int i=1;i<=cnt;i++)
  {
    car[i].pos=read();
    car[i].id=i;
  }
  for(int i=1;i<=cnt;i++)
    car[i].v=read();
  sort(car+1,car+cnt+1,comp);
  int tot=1;
  for(int i=2;i<=cnt;i++)
  {
      if(car[i].v!=car[i-1].v||(car[i].v==car[i-1].v&&car[i].pos==car[i-1].pos))
        tot++;
      car[tot]=car[i];
  }
  cnt=tot,tot=0;
  a[++tot]=car[1];
  ans[1]=car[1].id;
  for(int i=2;i<=cnt;i++)
  {
    while(tot>=1&&interx(a[tot],car[i])<-minn)  tot--;
    while(tot>=2&&jud(a[tot-1],a[tot],car[i])) tot--; 
    a[++tot]=car[i];
    ans[tot]=car[i].id;
  }
  sort(ans+1,ans+tot+1);
  cout<<tot<<endl; 
  for(int i=1;i<=tot;i++)
  {
    printf("%d",ans[i]);
    if(i!=tot)printf(" ");
  }
  return 0;
}