archery.cpp

archery.cpp

#include <cstdio> // nice T_T...
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 100100
#define INF 1000010000
#define eps (1e-16)
#define pi 3.1415926535898
#define tpi 6.2831853071796
using namespace std;
struct point {
	double x,y;
	point(double x = 0,double y = 0): x(x), y(y) { }
} dot[maxn << 1];

struct line {
	point p,v;
	int num;
	double ang;
} L[maxn << 1], *que[maxn << 1];

point operator + (point a,point b) { return point(a.x + b.x, a.y + b.y); }
point operator - (point a,point b) { return point(a.x - b.x, a.y - b.y); }
point operator * (point a,double b) { return point(a.x * b,a.y * b); }
double operator * (point a,point b) { return a.x * b.x + a.y * b.y; }
double operator / (point a,point b) { return a.x * b.y - a.y * b.x; } 
int i,j,k,l,m,n,tot,s,t,x,y,ny,r,mid;

int sig(double a) {
	return (a < -eps ? -1 : (a > eps));
}

double length(point a) {
	return sqrt(a * a);
}

bool cmp(const line &a,const line &b) {
	return (a.ang < b.ang);
}

point cross_line(line &a,line &b) {
	point u = a.p - b.p;
	if (!sig(a.v / b.v)) return point(INF,INF);
	double t = (b.v / u) / (a.v / b.v);
	return a.p + a.v * t;
}

bool dot_R(point &a,line &b) {
	return sig((a - b.p) / b.v) > 0;
} // 判断a是否在b的右方

bool judge() { // 半平面交主过程，因为新加入的半平面可能使队列末端的半平面OOXX，所以用deque
	s = t = 1;
	int i,j,k;
	for (i = 1; L[i].num > tot; i++);
	que[t] = &L[i++];
	for (; i <= tot; i++) {
		if (L[i].num > mid) continue;
		while (s < t && dot_R(dot[t - 1],L[i])) t--;
		while (s < t && dot_R(dot[s],L[i])) s++;
		que[++t] = &L[i];
		if (s < t && !sig(fabs(que[t] -> ang - que[t - 1] -> ang)) > 0) {
			t--;
			if (!dot_R(L[i].p,*que[t])) que[t] = &L[i];
		} //平行且同向的半平面 特殊处理 选靠左的
		if (s < t) dot[t - 1] = cross_line(*que[t - 1],*que[t]);
 	}
	while (s < t && dot_R(dot[t - 1],*que[s])) t--; //具体作用？ 删除无用平面 因为肯能后面新加入的半平面会被前面的半平面更新
	if (t - s <= 1) return false;
	return true;
}

int main() {
	freopen("archery.in","r",stdin);
	freopen("archery.out","w",stdout);
	scanf("%d",&n);
	for (i = 1; i <= n; i++) {
		scanf("%d %d %d",&x,&y,&ny);
		L[++tot].p = point(0, (double) y / (double) x);
		L[tot].v = point(1, -x); L[tot].num = i;
		L[tot].ang = tpi - acos(1.0 / length(L[tot].v));
		L[++tot].p = point(0, (double) ny / (double) x);
		L[tot].v = point(-1, x); L[tot].num = i;
		L[tot].ang = L[tot - 1].ang - pi;
	}
	L[++tot].p = point(INF,0); L[tot].v = point(0,INF); L[tot].ang = pi / 2.0;
	L[++tot].p = point(0,INF); L[tot].v = point(-INF,0); L[tot].ang = pi;
	L[++tot].p = point(-INF,0); L[tot].v = point(0,-INF); L[tot].ang = pi * 1.5;
	L[++tot].p = point(0,-INF); L[tot].v = point(INF,0); L[tot].ang = 0;
	sort(L + 1,L + tot + 1,cmp);
	l = 1; r = n;
	while (l < r) {
		mid = (l + r + 1) >> 1;
		if (judge()) l = mid;
		else r = mid - 1;
	}
	printf("%d\n",l);
	return 0;
}