记录编号	485402	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]射箭	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	0.753 s
提交时间	2018-01-31 13:39:49	内存使用	27.02 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 100010
#define db double
db x[N],yy[N],y2[N];
struct Vector
{
	db x,y;
	Vector(db a=0,db b=0){x=a,y=b;}
	inline Vector operator + (const Vector &b)const {return Vector(x+b.x,y+b.y);}
	inline Vector operator - (const Vector &b)const {return Vector(x-b.x,y-b.y);}
	inline db operator * (const Vector &b)const {return x*b.y-b.x*y;}
	inline Vector operator * (const db &b)const {return Vector(x*b,y*b);}
}p[N];
struct line
{
	Vector s,t,v;db k;int id;
}l[N<<1],q[N<<1];int hd,tl;
inline bool mt (const line &a,const line &b)
{
	if(a.k!=b.k)return a.k<b.k;
	return (b.t-a.s)*a.v>0;
}
inline bool overwatch(Vector a,line b){return (b.s-a)*(b.t-a)<0;}
inline Vector cross(line a,line b)
{
	db l1=(a.t-b.s)*b.v,l2=b.v*(a.s-b.s);
	return a.s+a.v*(l2/(l1+l2));
}
int len;
inline void solve(int le,int r)
{
	if(le==r){printf("%d\n",le);return;}
	register int mi=(le+r)>>1,i,last=1;
	hd=1,tl=0;
	for(i=1;i<=len;++i)
		if(l[i].id<=mi+1)
		{
			while(hd<tl&&overwatch(cross(q[tl],q[tl-1]),l[i]))--tl;
			while(hd<tl&&overwatch(cross(q[hd],q[hd+1]),l[i]))++hd;
			q[++tl]=l[i];
		}
	while(hd<tl&&overwatch(cross(q[tl],q[tl-1]),q[hd]))--tl;
	tl-hd>1?solve(mi+1,r):solve(le,mi);
}
char B[1<<15],*S=B,*T=B;
#define getc ((S==T)&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
inline int read()
{
	int x=0;register char c=getc;
	while(c<'0'|c>'9')c=getc;
	while(c>='0'&c<='9')x=10*x+(c^48),c=getc;
	return x;
}
int main()
{
	// freopen("Ark.in","r",stdin);
	freopen("bzoj_2732.in","r",stdin);
	freopen("bzoj_2732.out","w",stdout);
	register int i,j,cnt,n;
	n=read();
	for(i=1;i<=n;++i)
		x[i]=read(),yy[i]=read(),y2[i]=read();
	for(i=1;i<=n;++i)
	{
		l[i].s=Vector(0,yy[i]/x[i]);
		l[i].v=Vector(1,-x[i]);
		l[i].t=l[i].s+l[i].v;
		l[i].k=atan2(l[i].v.y,l[i].v.x);
		l[i].id=i;
		l[i+n].s=Vector(0,y2[i]/x[i]);
		l[i+n].v=Vector(-1,x[i]);
		l[i+n].t=l[i+n].s+l[i+n].v;
		l[i+n].k=atan2(l[i+n].v.y,l[i+n].v.x);
		l[i+n].id=i;
	}
	len=n<<1;
	l[++len].s=Vector(0,0),l[len].v=Vector(0,1),l[len].t=Vector(0,1),l[len].k=atan2(1,0);l[len].id=0;
	l[++len].s=Vector(0,0),l[len].v=Vector(1,0),l[len].t=Vector(1,0),l[len].k=atan2(0,1);l[len].id=0;
	sort(l+1,l+len+1,mt);
	for(cnt=1,i=2;i<=len;++i)
		if(l[i].k!=l[cnt].k)l[++cnt]=l[i];
	len=cnt;
	solve(1,n);
}