记录编号	376730	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]射箭	最终得分	100
用户昵称	New World	是否通过	通过
代码语言	C++	运行时间	2.478 s
提交时间	2017-02-28 06:23:54	内存使用	14.05 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define double long double
#define Inf 2e100
#define eps 1e-12
const int maxn=200050;
struct Point{
	double x,y;
	Point(double xx=0,double yy=0){x=xx;y=yy;}
	void input(){scanf("%lf%lf",&x,&y);}
	void output(){printf("<<%.3lf %.3lf>>",x,y);}
};
typedef Point Vector;

Vector operator - (Point A,Point B)
{return Vector(A.x-B.x,A.y-B.y);}

Point operator + (Point A,Vector B)
{return Point(A.x+B.x,A.y+B.y);}

Vector operator * (Vector A,double x)
{return Vector(A.x*x,A.y*x);}

double Cross(Vector A,Vector B)
{return A.x*B.y-A.y*B.x;}

int dcmp(double x)
{return fabs(x)<eps ? 0 : x>0 ? 1 : -1;}

struct Line{
	Point P;Vector v;
	double ang;
	Line(){};
	Line(Point A,Vector B){
		P=A;v=B;
		ang=atan2(v.y,v.x);
	}
};

bool operator < (Line A,Line B)
{return A.ang<B.ang;}

bool OnLeft(Line L,Point P)
{return dcmp(Cross(L.v,P-L.P))>=0;}

Point LineInterSection(Line L1,Line L2){
	Vector u=L1.P-L2.P;
	double t=Cross(L2.v,u)/Cross(L1.v,L2.v);
	return L1.P+L1.v*t;
}

bool HalfPlaneInterSection(Line *L,int n){
	sort(L,L+n);
	static Line *q=new Line[n];
	static Point *p=new Point[n];
	int head,tail;
	q[head=tail=0]=L[0];
	for(int i=1;i<n;i++){
		while(head<tail && !OnLeft(L[i],p[tail-1]))tail--;
		while(head<tail && !OnLeft(L[i],p[head  ]))head++;
		q[++tail]=L[i];
		if(dcmp(Cross(q[tail].v,q[tail-1].v))==0){
			tail--;
			if(OnLeft(q[tail],L[i].P))q[tail]=L[i];
		}
		if(head<tail)p[tail-1]=LineInterSection(q[tail],q[tail-1]);
	}
	while(head<tail && !OnLeft(q[head],p[tail-1]))tail--;
	if(tail-head<=1)return false;
	return true;
}

int n,cnt;
struct Oper{
	int x,y1,y2;//y1<y2
	void input(){scanf("%d%d%d",&x,&y1,&y2);}
}oper[maxn];

Line L[maxn];
void Copy(int num){
	cnt=0;
	for(int i=1;i<=num;i++){
		double k=-oper[i].x;
		double b=(double)oper[i].y1/oper[i].x;
		L[cnt++]=Line(Point(0,b),Vector(1,k));
			   k=-oper[i].x;
			   b=(double)oper[i].y2/oper[i].x;
        L[cnt++]=Line(Point(0,b),Vector(-1,-k));
   }
}
void Init();
int main(){
	//freopen("test.in","r",stdin);freopen("test.out","w",stdout);
	freopen("bzoj_2732.in","r",stdin);freopen("bzoj_2732.out","w",stdout);
    Init();
    return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)oper[i].input();
	int l=1,r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		Copy(mid);
		if(HalfPlaneInterSection(L,cnt))l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",r);
}