#include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <stack>
using namespace std;
#define DEBUG 0
#define MAXN 200011
template <typename T> T sq(T x) { return x * x; }
const double eps = 1e-12, pi = acos(-1.0); int sgn(double x) { return x < -eps ? -1 : (x > eps ? 1 : 0); }
struct VEC { double x, y; bool operator == (const VEC& b) const { return sgn(x - b.x) == 0 && sgn(y - b.y) == 0; } bool operator < (const VEC& b) const { return sgn(y - b.y) == 0 ? sgn(x - b.x) < 0 : y < b.y; }
VEC operator - (const VEC& b) const { return VEC{x - b.x, y - b.y}; } VEC operator + (const VEC& b) const { return VEC{x + b.x, y + b.y}; }
double len() const { return hypot(x, y); } double dist(const VEC& b) const { return (*this - b).len(); }
double len2() const { return sq(x) + sq(y); } double dist2(const VEC& b) const { return (*this - b).len2(); }
VEC operator * (double k) const { return VEC{x * k, y * k}; } VEC trunc(double l) const { double ori = len(); if (!sgn(ori)) return *this; return *this * (l / ori); }
VEC operator / (double k) const { return VEC{x / k, y / k}; } VEC norm() const { return *this / len(); }
double operator ^ (const VEC& b) const { return x * b.y - y * b.x; } double operator * (const VEC& b) const { return x * b.x + y * b.y; } double rad_di(const VEC& b) const { return atan2(*this ^ b, *this * b); } double rad(const VEC& b) const { return fabs(rad_di(b)); }
VEC rotleft() const { return VEC{-y, x}; } VEC rotright() const { return VEC{y, -x}; } VEC rot(double a) const { double c = cos(a), s = sin(a); return VEC{x * c - y * s, x * s + y * c}; }
double slope() const { double ans = atan2(y, x); if (sgn(ans) < 0) ans += pi; else if (sgn(ans - pi) == 0) ans -= pi; return ans; }
double cross(const VEC& p1, const VEC& p2) const { return (p1 - *this) ^ (p2 - *this); }
int relation(const VEC& b) const { return sgn(b ^ *this); }
VEC operator - () const { return VEC{-x, -y}; } bool SameDi(const VEC& b) const { return sgn(x) == sgn(b.x) && sgn(y) == sgn(b.y); }
void input() { scanf("%lf%lf", &x, &y); } };
struct LINE { VEC s, v; void set(const VEC& _s, double a) { s = _s; v = {cos(a), sin(a)}; } void set(double a, double b, double c) { v = {b, -a}; s = fabs(a) > fabs(b) ? VEC{-c / a, 0} : VEC{0, -c / b}; }
int relation(const VEC& p) const { return sgn((p - s) ^ v); } int relation(const LINE& b) const { if (v.relation(b.v) == 0) return b.relation(s) == 0; return 2; }
VEC CrossPoint(const LINE& b) const { double t = ((b.s - s) ^ b.v) / (v ^ b.v); return s + v * t; }
double dist_di(const VEC& p) const { return (v ^ (p - s)) / v.len(); } double dist(const VEC& p) const { return fabs(dist_di(p)); }
VEC projection(const VEC& p) const { VEC v1 = v.norm(); return v1 * ((p - s) * v1) + s; } VEC symmetry(const VEC& p) const { VEC p0 = projection(p); return p0 * 2 - p; }
void SetAngularBisector(const VEC& a, const VEC& b, const VEC& c) { set(a, (atan2(b.y - a.y, b.x - a.x) + atan2(c.y - a.y, c.x - a.x)) / 2); }
LINE operator - () const { return LINE{s, -v}; } };
namespace HalfPlane { int di(const LINE& a, const LINE& b) { int rel = a.v.relation(b.v); if (0 == rel) { if (a.v.SameDi(b.v)) { return a.relation(b.s); } else { return -2; } } else { return rel; } } bool Infinite(const LINE ls[], int n) { stack<int> sta; LINE s = ls[0]; LINE t = -ls[0]; for (int i = 1; i < n; ++i) { int rel = di(s, ls[i]); if (-2 == rel) { sta.push(i); } else if (rel < 0) { s = ls[i]; if (di(t, s) < 0) return false; } else if (rel > 0) { rel = di(t, -ls[i]); if (rel > 0) { t = -ls[i]; if (di(s, t) > 0) return false; } } } while (!sta.empty()) { int i = sta.top(); sta.pop(); if (0 == ls[i].v.relation(s.v)) { if (s.relation(ls[i].s) <= 0) { s.s = ls[i].s; } else { return false; } } else if (ls[i].v.relation(t.v) || t.relation(ls[i].s) < 0) { return false; } } if (s.v.relation(t.v)) { return true; } else { if (s.v.SameDi(-t.v)) return true; else return s.relation(t.s) <= 0; } }
int que[MAXN]; VEC cp[MAXN]; int st, ed;
int Intersection(const LINE ls[], int n) { static pair<double, int> ord[MAXN];
for (int i = 0; i < n; ++i) ord[i] = make_pair(atan2(ls[i].v.y, ls[i].v.x), i); sort(ord, ord + n); int m = 0; for (int i = 1; i < n; ++i) if (sgn(ord[i].first - ord[m].first)) ord[++m] = ord[i]; else if (ls[ord[m].second].relation(ls[ord[i].second].s) == -1) ord[m] = ord[i]; n = m + 1; if (Infinite(ls, n)) return 2; que[st=0] = ord[0].second; que[ed=1] = ord[1].second; cp[1] = ls[ord[1].second].CrossPoint(ls[ord[0].second]); for (int i = 2; i < n; ++i) { const LINE &now = ls[ord[i].second]; while (st < ed && now.relation(cp[ed]) == 1) --ed; while (st < ed && now.relation(cp[st + 1]) == 1) ++st; if (now.v.relation(ls[que[ed]].v) == 0) return 0; que[++ed] = ord[i].second; cp[ed] = now.CrossPoint(ls[que[ed - 1]]); } while (st < ed && ls[que[st]].relation(cp[ed]) == 1) --ed; while (st < ed && ls[que[ed]].relation(cp[st + 1]) == 1) ++st; return st + 1 < ed; } void GetConvex(VEC ps[], int& n, const LINE ls[]) { n = ed - st + 1; memcpy(ps, cp + st, n * sizeof(VEC)); } }
int main() { int n; static double x[MAXN], y1[MAXN], y2[MAXN]; static LINE ls[MAXN << 1];
scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%lf%lf%lf", x + i, y1 + i, y2 + i); }
int tot = 0; ls[tot++] = LINE{VEC{0, 0}, VEC{1, 0}}; ls[tot++] = LINE{VEC{0, 0}, VEC{0, 1}}; for (int i = 0; i < n; ++i) { ls[tot++] = LINE{VEC{0, y1[i] / x[i]}, VEC{1, -x[i]}}; ls[tot++] = LINE{VEC{0, y2[i] / x[i]}, VEC{-1, x[i]}}; } #if DEBUG for (int i = 0; i < tot; ++i) { printf("%f %f %f %f\n", ls[i].s.x, ls[i].s.y, ls[i].v.x, ls[i].v.y); } #endif int L = 0, R = n-1, ans = -1; while (L <= R) { int mid = (L + R) >> 1; if (HalfPlane::Intersection(ls, (mid + 2) << 1)) { ans = mid; L = mid + 1; } else { R = mid - 1; } } printf("%d\n", ans + 1); return 0; }
|