Advertisement
kuchumov

Untitled

May 12th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.24 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <string>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <set>
  9. #include <map>
  10. #include <cmath>
  11. #include <ctime>
  12. #include <functional>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <valarray>
  16. #include <complex>
  17. #include <queue>
  18. #include <cassert>
  19. #include <bitset>
  20. using namespace std;
  21.  
  22. #ifdef LOCAL
  23. #define debug_flag 1
  24. #else
  25. #define debug_flag 0
  26. #endif
  27.  
  28.     template <class T1, class T2 >
  29. std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p)
  30. {
  31.     os << "[" << p.first << ", " << p.second << "]";
  32.     return os;
  33. }
  34.  
  35.     template <class T >
  36. std::ostream& operator << (std::ostream& os, const std::vector<T>& v)
  37. {
  38.     os << "[";
  39.     bool first = true;
  40.     for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
  41.     {
  42.         if (!first)
  43.             os << ", ";
  44.         first = false;
  45.         os << *it;
  46.     }
  47.     os << "]";
  48.     return os;
  49. }
  50.  
  51. #define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }
  52.  
  53. vector<string> _split(const string& s, char c) {
  54.     vector<string> v;
  55.     stringstream ss(s);
  56.     string x;
  57.     while (getline(ss, x, c))
  58.         v.emplace_back(x);
  59.     return v;
  60. }
  61.  
  62. void _print(vector<string>::iterator) {}
  63. template<typename T, typename... Args>
  64. void _print(vector<string>::iterator it, T a, Args... args) {
  65.     string name = it -> substr((*it)[0] == ' ', it -> length());
  66.     if (isalpha(name[0]))
  67.         cerr << name  << " = " << a << " ";
  68.     else
  69.         cerr << name << " ";
  70.     _print(++it, args...);
  71. }
  72.  
  73. typedef long long int int64;
  74.  
  75. __float128 aaa;
  76. typedef long double ldouble;
  77.  
  78. const ldouble EPS = 1e-25;
  79. const ldouble PI = acosl(-1);
  80.  
  81. bool eq(ldouble a, ldouble b)
  82. {
  83.     return fabsl(a - b) < EPS;
  84. }
  85.  
  86. bool ls(ldouble a, ldouble b)
  87. {
  88.     return a < b && !eq(a, b);
  89. }
  90.  
  91. bool gr(ldouble a, ldouble b)
  92. {
  93.     return a > b && !eq(a, b);
  94. }
  95.  
  96. bool ls_eq(ldouble a, ldouble b)
  97. {
  98.     return a < b || eq(a, b);
  99. }
  100.  
  101. bool gr_eq(ldouble a, ldouble b)
  102. {
  103.     return a > b || eq(a, b);
  104. }
  105.  
  106. ldouble sqr(ldouble a)
  107. {
  108.     return a * a;
  109. }
  110.  
  111. struct Point
  112. {
  113.     ldouble x, y;
  114.  
  115.     Point() : x(), y() {}
  116.     Point(ldouble _x, ldouble _y) : x(_x), y(_y) {}
  117.  
  118.     void scan()
  119.     {
  120.         scanf("%Lf%Lf", &x, &y);
  121.     }
  122.  
  123.     bool operator == (const Point &p) const
  124.     {
  125.         return eq(x, p.x) && eq(y, p.y);
  126.     }
  127.  
  128.     bool operator != (const Point &p) const
  129.     {
  130.         return !(*this == p);
  131.     }
  132.  
  133.     Point operator + (const Point & p) const { return Point{x + p.x, y + p.y}; }
  134.  
  135.     Point operator - (const Point & p) const { return Point{x - p.x, y - p.y}; }
  136.  
  137.     Point operator * (const ldouble &k) const
  138.     {
  139.         return Point(x * k, y * k);
  140.     }
  141.  
  142.     ldouble operator * (const Point &p) const { return x * p.y - y * p.x; }
  143.  
  144.     bool is_right() const { return gr(x, 0) || (eq(x, 0) && gr(y, 0)); }
  145.  
  146.     ldouble operator % (const Point & p) const { return x * p.x + y * p.y; }
  147.  
  148.     ldouble length() const { return sqrtl(*this % *this); }
  149.  
  150.     ldouble dist_to(const Point &p) const { return (*this - p).length(); }
  151.  
  152.     Point rotate() const
  153.     {
  154.         return Point(-y, x);
  155.     }
  156.  
  157.     Point rotate(ldouble alpha) const
  158.     {
  159.         return rotate(cosl(alpha), sinl(alpha));
  160.     }
  161.  
  162.     Point rotate(ldouble cosa, ldouble sina) const
  163.     {
  164.         return *this * cosa + rotate() * sina;
  165.     }
  166. };
  167.  
  168. std::ostream& operator << (std::ostream& os, const Point &p)
  169. {
  170.     os << "(" << p.x << ", " << p.y << ")";
  171.     return os;
  172. }
  173.  
  174. bool cmp_by_angle(const Point &a, const Point &b)
  175. {
  176.     if(a.is_right() != b.is_right())
  177.         return a.is_right();
  178.     return ls(a * b, 0);
  179. }
  180.  
  181. struct Line
  182. {
  183.     //!!!
  184.     //halfplane in negative direction
  185.     //!!!
  186.  
  187.     Point one, two;
  188.  
  189.     Line() : one(), two() {}
  190.     Line(Point _one, Point _two) : one(_one), two(_two) {}
  191.  
  192.     Point dir() const { return two - one; }
  193.  
  194.     bool operator < (const Line & b) const { return cmp_by_angle(dir(), b.dir()); }
  195.  
  196.     ldouble get_coeff(const Line & b) const
  197.     {
  198.         ldouble r = (b.dir() * (one - b.one)) / (dir() * b.dir());
  199.         return r;
  200.     }
  201.  
  202.     bool is_parallel(const Line & b) const { return eq(dir() * b.dir(), 0); }
  203.  
  204.     bool is_better(const Line & b) const
  205.     {
  206.         //assert(is_parallel(b));
  207.         return ls((b.one - one) * (two - one), 0);
  208.     }
  209.  
  210.     bool is_below(const Line & a, const Line & c) const
  211.     {
  212.         return gr_eq(get_coeff(a), get_coeff(c));
  213.     }
  214.  
  215.     Point intersect(const Line & b) const
  216.     {
  217.         ldouble r = get_coeff(b);
  218.         return Point(one.x + r * (two - one).x, one.y + r * (two - one).y);
  219.     }
  220. };
  221.  
  222. deque<Line> get_hull(vector<Line> halfplanes)
  223. {
  224.     sort(halfplanes.begin(), halfplanes.end());
  225.     deque<Line> hull;
  226.     #define sec_back(vect) vect[(int) vect.size() - 2]
  227.     for(Line line : halfplanes) {
  228.         if(!hull.empty() && line.is_parallel(hull.back()))
  229.         {
  230.             if(hull.back().is_better(line))
  231.                 line = hull.back();
  232.             hull.pop_back();
  233.         }
  234.         while((int) hull.size() >= 2 && hull.back().is_below(sec_back(hull), line))
  235.             hull.pop_back();
  236.         hull.push_back(line);
  237.     }
  238.     while((int) hull.size() >= 3) {
  239.         if(hull.back().is_below(sec_back(hull), hull[0]))
  240.             hull.pop_back();
  241.         else if(hull[0].is_below(hull.back(), hull[1]))
  242.             hull.pop_front();
  243.         else break;
  244.     }
  245.     #undef sec_back
  246.     return hull;
  247. }
  248.  
  249. const int N = (int)3e5;
  250.  
  251. int n;
  252. int64 x_list[N], y1_list[N], y2_list[N];
  253. vector<Line> planes;
  254.  
  255. void add_plane(ldouble a, ldouble b, ldouble c, bool is_less)
  256. {
  257.     Point A = Point(a * c / (sqr(a) + sqr(b)), b * c / (sqr(a) + sqr(b)));
  258.     Point B = A + Point(-b, a);
  259.    
  260.     //assert(eq(A.x * a + A.y * b, c));
  261.     //assert(eq(B.x * a + B.y * b, c));
  262.     //assert(A != B);
  263.  
  264.     Point C = A + (B - A).rotate(-PI / 2);
  265.     ldouble cc = C.x * a + C.y * b;
  266.     //assert(!eq(cc, c));
  267.     if (is_less != (cc < c))
  268.         swap(A, B);
  269.    
  270.     planes.push_back(Line(A, B));
  271. }
  272.  
  273. bool can(int k)
  274. {
  275.     planes.clear();
  276.  
  277.     const int MAX_C = 1e9;
  278.  
  279.     vector<Point> corners {
  280.         Point{-MAX_C, MAX_C},
  281.         Point{MAX_C, MAX_C},
  282.         Point{MAX_C, -MAX_C},
  283.         Point{-MAX_C, -MAX_C}
  284.     };
  285.  
  286.     for(int i = 0; i < (int) corners.size(); i++)
  287.     {
  288.         int ni = (i + 1) % corners.size();
  289.         planes.push_back(Line(corners[i], corners[ni]));
  290.     }
  291.  
  292.     for (int i = 0; i < k; i++)
  293.     {
  294.         ldouble x0 = x_list[i];
  295.         ldouble y1 = y1_list[i];
  296.         ldouble y2 = y2_list[i];
  297.  
  298.         add_plane(x0 * x0, x0, y2, true);
  299.         add_plane(x0 * x0, x0, y1, false);
  300.     }
  301.  
  302.     for (Line p : planes)
  303.         dbg(p.one, p.two);
  304.  
  305.     deque<Line> res = get_hull(planes);
  306.  
  307.     for (Line l : res)
  308.         dbg(l.one, l.two);
  309.  
  310.     if (res.size() >= 3)
  311.         return true;
  312.  
  313.     if (res.size() <= 1)
  314.         return false;
  315.  
  316.  
  317.     Point AA = res[0].intersect(res[1]);
  318.  
  319.     bool good = true;
  320.  
  321.     for (Line l : planes)
  322.         if (gr((l.two - l.one) * (AA - l.one), 0))
  323.             good = false;
  324.  
  325.     return good;
  326. }
  327.  
  328. void test()
  329. {
  330.     const int MAX_C = 1e9;
  331.  
  332.     vector<Point> corners {
  333.         Point{-MAX_C, MAX_C},
  334.         Point{MAX_C, MAX_C},
  335.         Point{MAX_C, -MAX_C},
  336.         Point{-MAX_C, -MAX_C}
  337.     };
  338.  
  339.     planes.push_back(Line(Point(0, 0), Point(0, -1)));
  340.     planes.push_back(Line(Point(0, 0), Point(0, 1)));
  341.  
  342.     deque<Line> d = get_hull(planes);
  343.  
  344.     dbg(d.size());
  345. }
  346.  
  347. int main()
  348. {
  349. #ifdef LOCAL
  350.     freopen ("input.txt", "r", stdin);
  351. #endif
  352.  
  353.     //test();
  354.     //return 0;
  355.  
  356.     scanf("%d", &n);
  357.     for (int i = 0; i < n; i++)
  358.         scanf("%lld%lld%lld", &x_list[i], &y1_list[i], &y2_list[i]);
  359.  
  360.     int l = 1;
  361.     int r = n + 1;
  362.  
  363.     while (r - l > 1)
  364.     {
  365.         int mid = (l + r) / 2;
  366.         if (can(mid))
  367.             l = mid;
  368.         else
  369.             r = mid;
  370.     }
  371.  
  372.     printf("%d\n", l);
  373.  
  374.     return 0;
  375. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement