记录编号	367360	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012]射箭	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.006 s
提交时间	2017-01-30 11:53:40	内存使用	27.75 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
const int N=4e5+10;
const db pi=acos(-1.0);
int n,head,tail,cnt;
struct pt{
	db x,y;
	pt(db X=0,db Y=0){x=X;y=Y;}
};
struct line{//ax+by+c>=0
	db a,b,c,angle;int id;
	line(db A=0,db B=0,db C=0,int ID=0){
		a=A;b=B;c=C;id=ID;
		A=abs(A);
		if (A>0) a/=A,b/=A,c/=A;
		angle=atan2(b,a);//angle为该半平面法向量的极角 
	}
	bool operator < (const line x)const{
		return angle!=x.angle?angle<x.angle:c>x.c;
	}
}a[N],q[N];
pt point(line x,line y){//返回x和y的交点 
	db d=x.a*y.b-x.b*y.a;
	return pt((x.b*y.c-y.b*x.c)/d,(x.c*y.a-x.a*y.c)/d);
}
bool check(line x,line y,line l){
	pt a=point(x,y);
	return a.x*l.a+a.y*l.b+l.c<0;
}
void solve(int l,int r){
	if (l==r) return (void)printf("%d\n",l);
	int mid=(l+r)>>1,last=0;
	n=mid+1;head=1;tail=0;
	for (int i=1;i<=cnt;i++)
	if (a[i].id<=n&&a[i].angle!=a[last].angle){
		for (;head<tail&&check(q[tail],q[tail-1],a[i]);tail--);
		for (;head<tail&&check(q[head],q[head+1],a[i]);head++);
		q[++tail]=a[i];last=i;
	}
	for (;head<tail&&check(q[tail],q[tail-1],q[head]);tail--);
	for (;head<tail&&check(q[head],q[head+1],q[tail]);head++);
	tail-head>1?solve(mid+1,r):solve(l,mid);
}
int main()
{
	freopen("bzoj_2732.in","r",stdin);
	freopen("bzoj_2732.out","w",stdout);
	scanf("%d",&n);
	a[++cnt]=line(0,1,0,0);//b>=0
	a[++cnt]=line(-1,0,0,0);//a<=0
	for (int i=1;i<=n;i++){
		db x,y1,y2;
		scanf("%lf%lf%lf",&x,&y1,&y2);
		a[++cnt]=line(x*x,x,-y1,i);
		a[++cnt]=line(-x*x,-x,y2,i);
	}
	sort(a+1,a+cnt+1);
	a[0].angle=-1e10;
	//for (int i=1;i<=cnt;i++) printf("%d ",a[i].id);puts("");
	solve(1,n);
	return 0;
}