记录编号	107074	评测结果	AAAAAAAAAA
题目名称	[JLOI 2013] 赛车	最终得分	100
用户昵称	raywzy	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2014-06-22 14:07:19	内存使用	0.66 MiB

#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fin("race1.in");
ofstream fout("race1.out");
class New
{
public:int number;int k;int s;
}A[10001];
int Stack[10001]; int D[10001],F[10001];
New a[10001];
int ZZ=0,N;
void push(int a)
{
	ZZ++;Stack[ZZ]=a;
}
void pop()
{
	ZZ--;
}
bool Rule(New a,New b)
{
	if(a.k<b.k)
		return 1;
	if(a.k==b.k && a.s<b.s)return 1;
	return 0;
}
int main()
{
	bool flag=0;
	bool p=0;
	int i,B,C; fin>>N;
	//统计交点个数以及其x坐标，用F数组表示，sum计数
	int sum=0;
	double F[10001];
	double LSX=0,temp;
	for(i=1;i<=N;i++)
		fin>>D[i];
	for(i=1;i<=N;i++)
		fin>>F[i];
	for(i=1;i<=N;i++)
	{
		a[i].s=D[i];
		a[i].k=F[i];
		A[i].number=i;
		A[i].s=D[i];
		A[i].k=F[i];
	}
	sort(A+1,A+N+1,Rule);
	for(i=1;i<=N;i++)
	{
		if(ZZ==0)
		{
			push(A[i].number);
		    continue;
		}
/*	    while(a[A[i].number].k==a[Stack[ZZ]].k)
		{
			p=1;
			if(a[A[i].number].s>a[Stack[ZZ]].s)
			{
				pop;
				push(A[i].number);
			}
		}*/
		temp=double((a[Stack[ZZ]].s*1.0-a[A[i].number].s*1.0)/(a[A[i].number].k*1.0-a[Stack[ZZ]].k*1.0));//计算当前枚举的直线与栈顶直线交点
		if(temp>=F[sum])
		{
			sum++;F[sum]=temp;
			push(A[i].number);
			continue;
		}
		else
		{
			while(temp<F[sum])
			{
				pop();
				if(ZZ==0)
				{
					push(A[i].number);
					flag=1;
					break;
				}
				sum--;
				temp=double((a[Stack[ZZ]].s*1.0-a[A[i].number].s*1.0)/(a[A[i].number].k*1.0-a[Stack[ZZ]].k*1.0));
			}
			if(flag==1)
			{
				flag=0;
				continue;
			} 
			sum++;
			F[sum]=temp;
			push(A[i].number);
		}
	}
	fout<<ZZ<<endl;
	sort(Stack+1,Stack+ZZ+1);
	for(i=1;i<=ZZ;i++)
		fout<<Stack[i]<<' ';
	return 0;
}