鬼畜的半平面交

省选前学算法系列

%%%zzq

# include <stdio.h>
# include <stdlib.h>
# include <math.h>
# include <string.h>
# include <string>
# include <algorithm>
# include <vector>
# include <iostream>
# include <deque>

using namespace std;

/* ======== template ========= */

# define double long double

const double pi = acos(-1.0);
const double eps = 1e-18, meps = -eps, inf = 1111111111, minf = -inf;

inline double abs(double a) {
	return a<0 ? -a : a;
}

inline double max(double a, double b) {
	return a>b ? a : b;
}

inline double min(double a, double b) {
	return a<b ? a : b;
}

struct P {
	double x,y;
	P() {}
	P(double _x,double _y) : x(_x), y(_y) {}
	P operator +(P p) {
		return P(x+p.x, y+p.y);
	}
	P operator -(P p) {
		return P(x-p.x, y-p.y);
	}
	P operator *(double d) {
		return P(x*d, y*d);
	}
	double dot(P a) {
		return x*a.x+y*a.y;
	}
	double det(P a) {
		return x*a.y-y*a.x;
	}
};

inline double dist2(P a, P b) {
	return (a-b).dot(a-b);
}

inline double dist(P a, P b) {
	return sqrt(dist2(a, b));
}

//等于0:三点共线
//大于0:p0p2在p0p1的逆时针方向
//小于0:p0p2在p0p1的顺时针方向 
inline double direction(P p1, P p2, P p) {
	return (p1-p).det(p2-p);
}

inline bool dot3online(P p1, P p2, P p3) {
	return direction(p1, p2, p3) == 0;
}

inline bool on_segment(P p1, P p2, P q) {
	return dot3online(p1, p2, q) && (p1-q).dot(p2-q) <= 0;
}

inline P intersection(P p1, P p2, P q1, P q2) {
	return p1 + (p2-p1) * ((q2-q1).det(q1-p1) / (q2-q1).det(p2-p1));
}

inline bool cmp_x(const P& p, const P& q) {
	return p.x < q.x || (p.x == q.x && p.y < q.y);
}

inline bool segment_intersection(P p1, P p2, P q1, P q2) {
	double d1=direction(p1, q1, q2), d2=direction(p2, q1, q2),
	       d3=direction(q1, p1, p2), d4=direction(q2, p1, p2);
	if (d1*d2 < 0 && d3*d4 < 0) return true;
	else if (d1 == 0 && on_segment(q1, q2, p1)) return true;
    else if (d2 == 0 && on_segment(q1, q2, p2)) return true;
    else if (d3 == 0 && on_segment(p1, p2, q1)) return true;
    else if (d4 == 0 && on_segment(p1, p2, q2)) return true;
    return false;
}

inline double area(vector<P> vs) {
	double res = 0;
	int Sz = vs.size();
	for (int i=0; i<Sz; ++i) {
		int nxt = (i+1) % Sz;
		res += vs[i].det(vs[nxt]);
	}
	res = abs(res / 2.0);
	return res;
}

inline vector<P> convex_hull(vector<P> ps) {
	int n = ps.size();
	sort(ps.begin(), ps.end(), cmp_x);
	int k = 0;
	vector<P> qs(n*2);
	for (int i=0; i<n; ++i) {
		while(k>1 && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0) --k;
		qs[k++] = ps[i];
	}
	for (int i=n-2, t=k; i>=0; --i) {
		while(k>t && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0) --k;
		qs[k++] = ps[i];
	}
	qs.resize(k-1);
	return qs;
}

inline double rotating(vector<P> ps) {
	vector<P> qs = convex_hull(ps);
	int n = qs.size();
	if (n==2) return dist(qs[0], qs[1]);
	int i=0, j=0;
	for (int k = 0; k < n; ++k) {
        if(! cmp_x(qs[i], qs[k])) i = k;
        if(cmp_x(qs[j], qs[k])) j = k;
    }
    double res = 0.0;
    int si = i, sj = j;
    while(i != si || j != sj) {
		res = max(res, dist(qs[i], qs[j]));
		if ((qs[(i+1) % n] - qs[i]).det(qs[(j+1) % n] - qs[j]) < 0) i = (i+1) % n;
		else j = (j+1) % n;
    }
    return res;
}

inline void prtP(P a) {
    printf("(%lf,%lf)", a.x, a.y);
}

/* ============= template end ================*/

const int M=300010;

int n;

struct L{
	P a,b;
	int id;
	double k;
}s[M*2],t[M*2],Q[M*2];
int sn=0;

inline bool cmp_line(L a, L b) {
	if(a.k==b.k) return (a.b-a.a).det(b.a-a.a) > 0;
	else return a.k<b.k;
}

inline bool get(L a, L b, L c) {
	P point=intersection(a.a,a.b,b.a,b.b);
	return (point-c.a).det(c.b-c.a) > 0;
}


inline bool bpm(int g) {
	int an=0;
	for (int i=1; i<=sn; ++i) {
		if(s[i].id<=g) {
			if(s[i].k!=t[an].k) ++an;
			t[an]=s[i];
		}
	}
	//printf("%d\n",an);
	int le=1, ri=0;
	Q[++ri]=t[1], Q[++ri]=t[2];
	for (int i=3; i<=an; ++i) {
		while(le<ri && get(Q[ri-1],Q[ri],t[i])) ri--;
		while(le<ri && get(Q[le+1],Q[le],t[i])) le++;
		Q[++ri]=t[i];
	}
	while(le<ri && get(Q[ri-1],Q[ri],Q[le])) ri--;
	while(le<ri && get(Q[le+1],Q[le],Q[ri])) le++;
	return ri-le>=2;
}
int read() {
	int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main() {
	freopen("archery.in","r",stdin);
	freopen("archery.out","w",stdout);
	n=read();
	
	sn=0;
	s[++sn].a=P(minf, minf); s[sn].b=P(inf, minf);
	s[++sn].a=P(inf, minf); s[sn].b=P(inf, inf);
	s[++sn].a=P(inf, inf); s[sn].b=P(minf, inf);
	s[++sn].a=P(minf, inf); s[sn].b=P(minf, minf);
	
	double x, ay, by; int g1,g2,g3;
	for (int i=1; i<=n; ++i) {
		g1=read(),g2=read(),g3=read();
		x=g1,ay=g2,by=g3;
		s[++sn].a=P(-1, ay/x+x); s[sn].b=P(1, ay/x-x);
		s[++sn].a=P(1, by/x-x); s[sn].b=P(-1, by/x+x);
		s[sn].id=s[sn-1].id=i;
	}
	
	for (int i=1;i<=sn; ++i)
		s[i].k=atan2(s[i].b.y-s[i].a.y, s[i].b.x-s[i].a.x);
	
	sort(s+1, s+sn+1, cmp_line);
	
	int le=1, ri=n, ret=0;
	while(le <= ri) {
		int mi = le+ri >> 1;
		if (bpm(mi)) {
			ret=mi;
			le=mi+1;
		} else ri=mi-1;
	}
	
	printf("%d\n",ret);
	
	return 0;
}