Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <cmath>
- #include <ctime>
- #include <functional>
- #include <sstream>
- #include <fstream>
- #include <valarray>
- #include <complex>
- #include <queue>
- #include <cassert>
- #include <bitset>
- using namespace std;
- #ifdef LOCAL
- #define debug_flag 1
- #else
- #define debug_flag 0
- #endif
- template <class T1, class T2 >
- std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
- {
- os << "[" << p.first << ", " << p.second << "]";
- return os;
- }
- template <class T >
- std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
- {
- os << "[";
- bool first = true;
- for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
- {
- if (!first)
- os << ", ";
- first = false;
- os << *it;
- }
- os << "]";
- return os;
- }
- #define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }
- vector<string> _split(const string& s, char c) {
- vector<string> v;
- stringstream ss(s);
- string x;
- while (getline(ss, x, c))
- v.emplace_back(x);
- return v;
- }
- void _print(vector<string>::iterator) {}
- template<typename T, typename... Args>
- void _print(vector<string>::iterator it, T a, Args... args) {
- string name = it -> substr((*it)[0] == ' ', it -> length());
- if (isalpha(name[0]))
- cerr << name << " = " << a << " ";
- else
- cerr << name << " ";
- _print(++it, args...);
- }
- typedef long long int int64;
- __float128 aaa;
- typedef long double ldouble;
- const ldouble EPS = 1e-25;
- const ldouble PI = acosl(-1);
- bool eq(ldouble a, ldouble b)
- {
- return fabsl(a - b) < EPS;
- }
- bool ls(ldouble a, ldouble b)
- {
- return a < b && !eq(a, b);
- }
- bool gr(ldouble a, ldouble b)
- {
- return a > b && !eq(a, b);
- }
- bool ls_eq(ldouble a, ldouble b)
- {
- return a < b || eq(a, b);
- }
- bool gr_eq(ldouble a, ldouble b)
- {
- return a > b || eq(a, b);
- }
- ldouble sqr(ldouble a)
- {
- return a * a;
- }
- struct Point
- {
- ldouble x, y;
- Point() : x(), y() {}
- Point(ldouble _x, ldouble _y) : x(_x), y(_y) {}
- void scan()
- {
- scanf("%Lf%Lf", &x, &y);
- }
- bool operator == (const Point &p) const
- {
- return eq(x, p.x) && eq(y, p.y);
- }
- bool operator != (const Point &p) const
- {
- return !(*this == p);
- }
- Point operator + (const Point & p) const { return Point{x + p.x, y + p.y}; }
- Point operator - (const Point & p) const { return Point{x - p.x, y - p.y}; }
- Point operator * (const ldouble &k) const
- {
- return Point(x * k, y * k);
- }
- ldouble operator * (const Point &p) const { return x * p.y - y * p.x; }
- bool is_right() const { return gr(x, 0) || (eq(x, 0) && gr(y, 0)); }
- ldouble operator % (const Point & p) const { return x * p.x + y * p.y; }
- ldouble length() const { return sqrtl(*this % *this); }
- ldouble dist_to(const Point &p) const { return (*this - p).length(); }
- Point rotate() const
- {
- return Point(-y, x);
- }
- Point rotate(ldouble alpha) const
- {
- return rotate(cosl(alpha), sinl(alpha));
- }
- Point rotate(ldouble cosa, ldouble sina) const
- {
- return *this * cosa + rotate() * sina;
- }
- };
- std::ostream& operator << (std::ostream& os, const Point &p)
- {
- os << "(" << p.x << ", " << p.y << ")";
- return os;
- }
- bool cmp_by_angle(const Point &a, const Point &b)
- {
- if(a.is_right() != b.is_right())
- return a.is_right();
- return ls(a * b, 0);
- }
- struct Line
- {
- //!!!
- //halfplane in negative direction
- //!!!
- Point one, two;
- Line() : one(), two() {}
- Line(Point _one, Point _two) : one(_one), two(_two) {}
- Point dir() const { return two - one; }
- bool operator < (const Line & b) const { return cmp_by_angle(dir(), b.dir()); }
- ldouble get_coeff(const Line & b) const
- {
- ldouble r = (b.dir() * (one - b.one)) / (dir() * b.dir());
- return r;
- }
- bool is_parallel(const Line & b) const { return eq(dir() * b.dir(), 0); }
- bool is_better(const Line & b) const
- {
- //assert(is_parallel(b));
- return ls((b.one - one) * (two - one), 0);
- }
- bool is_below(const Line & a, const Line & c) const
- {
- return gr_eq(get_coeff(a), get_coeff(c));
- }
- Point intersect(const Line & b) const
- {
- ldouble r = get_coeff(b);
- return Point(one.x + r * (two - one).x, one.y + r * (two - one).y);
- }
- };
- deque<Line> get_hull(vector<Line> halfplanes)
- {
- sort(halfplanes.begin(), halfplanes.end());
- deque<Line> hull;
- #define sec_back(vect) vect[(int) vect.size() - 2]
- for(Line line : halfplanes) {
- if(!hull.empty() && line.is_parallel(hull.back()))
- {
- if(hull.back().is_better(line))
- line = hull.back();
- hull.pop_back();
- }
- while((int) hull.size() >= 2 && hull.back().is_below(sec_back(hull), line))
- hull.pop_back();
- hull.push_back(line);
- }
- while((int) hull.size() >= 3) {
- if(hull.back().is_below(sec_back(hull), hull[0]))
- hull.pop_back();
- else if(hull[0].is_below(hull.back(), hull[1]))
- hull.pop_front();
- else break;
- }
- #undef sec_back
- return hull;
- }
- const int N = (int)3e5;
- int n;
- int64 x_list[N], y1_list[N], y2_list[N];
- vector<Line> planes;
- void add_plane(ldouble a, ldouble b, ldouble c, bool is_less)
- {
- Point A = Point(a * c / (sqr(a) + sqr(b)), b * c / (sqr(a) + sqr(b)));
- Point B = A + Point(-b, a);
- //assert(eq(A.x * a + A.y * b, c));
- //assert(eq(B.x * a + B.y * b, c));
- //assert(A != B);
- Point C = A + (B - A).rotate(-PI / 2);
- ldouble cc = C.x * a + C.y * b;
- //assert(!eq(cc, c));
- if (is_less != (cc < c))
- swap(A, B);
- planes.push_back(Line(A, B));
- }
- bool can(int k)
- {
- planes.clear();
- const int MAX_C = 1e9;
- vector<Point> corners {
- Point{-MAX_C, MAX_C},
- Point{MAX_C, MAX_C},
- Point{MAX_C, -MAX_C},
- Point{-MAX_C, -MAX_C}
- };
- for(int i = 0; i < (int) corners.size(); i++)
- {
- int ni = (i + 1) % corners.size();
- planes.push_back(Line(corners[i], corners[ni]));
- }
- for (int i = 0; i < k; i++)
- {
- ldouble x0 = x_list[i];
- ldouble y1 = y1_list[i];
- ldouble y2 = y2_list[i];
- add_plane(x0 * x0, x0, y2, true);
- add_plane(x0 * x0, x0, y1, false);
- }
- for (Line p : planes)
- dbg(p.one, p.two);
- deque<Line> res = get_hull(planes);
- for (Line l : res)
- dbg(l.one, l.two);
- if (res.size() >= 3)
- return true;
- if (res.size() <= 1)
- return false;
- Point AA = res[0].intersect(res[1]);
- bool good = true;
- for (Line l : planes)
- if (gr((l.two - l.one) * (AA - l.one), 0))
- good = false;
- return good;
- }
- void test()
- {
- const int MAX_C = 1e9;
- vector<Point> corners {
- Point{-MAX_C, MAX_C},
- Point{MAX_C, MAX_C},
- Point{MAX_C, -MAX_C},
- Point{-MAX_C, -MAX_C}
- };
- planes.push_back(Line(Point(0, 0), Point(0, -1)));
- planes.push_back(Line(Point(0, 0), Point(0, 1)));
- deque<Line> d = get_hull(planes);
- dbg(d.size());
- }
- int main()
- {
- #ifdef LOCAL
- freopen ("input.txt", "r", stdin);
- #endif
- //test();
- //return 0;
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- scanf("%lld%lld%lld", &x_list[i], &y1_list[i], &y2_list[i]);
- int l = 1;
- int r = n + 1;
- while (r - l > 1)
- {
- int mid = (l + r) / 2;
- if (can(mid))
- l = mid;
- else
- r = mid;
- }
- printf("%d\n", l);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement