记录编号	489920	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]射箭	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	4.018 s
提交时间	2018-03-06 08:25:29	内存使用	25.75 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 200500
#define eps 1e-12
using namespace std;
struct point {
	double x[2];
	point (){}
	point (double a,double b){x[0]=a; x[1]=b;}
	double & operator [] (int a){return x[a];}
	point operator + (point a){return point (x[0]+a.x[0],x[1]+a.x[1]);}
	point operator - (point a){return point (x[0]-a.x[0],x[1]-a.x[1]);}
	double operator * (point a){return x[0]*a.x[1]-x[1]*a.x[0];}
}p[N];
struct line{
	point a,b;
	double alp;
	int id;
}l[N],q[N],tmp[N];
int n,tot,bot,top;
void addline(line &l,point a,point b,int id){
	l.a=a;l.b=b;l.id=id;
	l.alp=atan2(b[1]-a[1],b[0]-a[0]);
}
bool cmp(line a,line b){
	if(a.alp==b.alp)
		return (b.a-a.a)*(b.b-a.a)>=eps;
	return a.alp<b.alp;
}
point getpoint(line a,line b){
	point p;
	double dot1=(b.a-a.a)*(b.b-a.a);
	double dot2=(b.b-a.b)*(b.a-a.b);
	p[0]=(a.a[0]*dot2+a.b[0]*dot1)/(dot1+dot2);
	p[1]=(a.a[1]*dot2+a.b[1]*dot1)/(dot1+dot2);
	return p;
}
bool judge(line a,line b,line c){
	point p=getpoint (b,c);
	// printf("%lf  %lf\n",p[0],p[1]);
	// printf("%d  %d  %lf  %lf  %lf  %lf  %lf  %lf  %lf\n",b.id,c.id,p[0],p[1],a.a[0],a.a[1],a.b[0],a.b[1],(a.b-p)*(a.a-p));
	// printf("%lf  %lf  %lf  %lf\n",(a.b-p)[0],(a.b-p)[1],(a.a-p)[0],(a.a-p)[1]);
	return (a.b-p)*(a.a-p)>=eps;
}
bool check(int x){
	tot=0;
	register int i,j;
	// for(i=1;i<=tot;i++)
	// 	printf("%lf  %lf  %lf  %lf  %lf\n",l[i].a[0],l[i].a[1],l[i].b[0],l[i].b[1],l[i].alp);puts("");
	for(i=1;i<=2*n+2;i++)if(l[i].id<=x)
		tmp[++tot]=l[i];
	// sort(tmp+1,tmp+tot+1,cmp);
	for(i=2,j=1;i<=tot;i++)
		if(tmp[i].alp-tmp[j].alp>0)
			tmp[++j]=tmp[i];
	tot=j;
	// for(i=1;i<=tot;i++)
	// 	printf("%lf  %lf  %lf  %lf  %lf  %d\n",tmp[i].a[0],tmp[i].a[1],tmp[i].b[0],tmp[i].b[1],tmp[i].alp,tmp[i].id);puts("");
	bot=1;top=2;
	q[1]=tmp[1];q[2]=tmp[2];
	for(i=3;i<=tot;i++){
		while(top>bot&&judge(tmp[i],q[top-1],q[top]))top--;
		while(top>bot&&judge(tmp[i],q[bot+1],q[bot]))bot++;
		q[++top]=tmp[i];
		// printf("%d  %d  %d\n",i,tmp[i].id,top);
	}
	while(top>bot&&judge(q[bot],q[top-1],q[top]))top--;
	// for(i=bot;i<=top;i++)
	// 	printf("%lf  %lf  %lf  %lf  %lf  %d\n",q[i].a[0],q[i].a[1],q[i].b[0],q[i].b[1],q[i].alp,q[i].id);puts("");
	return top-bot>1;
}
int main(){
	freopen("bzoj_2732.in","r",stdin);
	freopen("bzoj_2732.out","w",stdout);
	scanf("%d",&n);
	register int i;
	double x,sy,ty;
	point a,b;
	for(int i=1;i<=n;i++){
		scanf("%lf%lf%lf",&x,&sy,&ty);
		a=point(0,sy/x),b=point(1,-x+sy/x);
		// printf("%lf  %lf  %lf  %lf\n",a[0],a[1],b[0],b[1]);
		addline(l[i*2-1],a,b,i);
		a=point(0,ty/x),b=point(1,-x+ty/x);
		// printf("%lf  %lf  %lf  %lf\n",b[0],b[1],a[0],a[1]);
		addline(l[i*2],b,a,i);
	}
	addline(l[n*2+1],point(0,0),point(0,1),0);
	addline(l[n*2+2],point(0,0),point(1,0),0);
	sort(l+1,l+2*n+3,cmp);
	// check(50000);return 0;
	int l=2,r=n,mid,ans=1;
	while(l<=r){
		mid=(l+r)>>1;
		if(check(mid))ans=mid,l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return 0;
}