fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MP make_pair
  3. #define PB push_back
  4. #define int long long
  5. #define st first
  6. #define nd second
  7. #define rd third
  8. #define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
  9. #define RE(i, n) FOR(i, 1, n)
  10. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  11. #define REP(i, n) for(int i = 0;i <(n); ++i)
  12. #define VAR(v, i) __typeof(i) v=(i)
  13. #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
  14. #define ALL(x) (x).begin(), (x).end()
  15. #define SZ(x) ((int)(x).size())
  16. #define __builtin_ctz __builtin_ctzll
  17. #define __builtin_clz __builtin_clzll
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<typename TH> void _dbg(const char* sdbg, TH h) { cerr<<sdbg<<"="<<h<<"\n"; }
  21. template<typename TH, typename... TA> void _dbg(const char* sdbg, TH h, TA... t) {
  22.   while(*sdbg != ',') { cerr<<*sdbg++; } cerr<<"="<<h<<","; _dbg(sdbg+1, t...);
  23. }
  24. #ifdef LOCAL
  25. #define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
  26. #define debugv(x) {{cerr <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<"\n"; }}
  27. #else
  28. #define debug(...) (__VA_ARGS__)
  29. #define debugv(x)
  30. #define cerr if(0)cout
  31. #endif
  32. #define next ____next
  33. #define prev ____prev
  34. #define left ____left
  35. #define hash ____hash
  36. typedef long long ll;
  37. typedef long double LD;
  38. typedef pair<int, int> PII;
  39. typedef pair<ll, ll> PLL;
  40. typedef vector<int> VI;
  41. typedef vector<VI> VVI;
  42. typedef vector<ll> VLL;
  43. typedef vector<pair<int, int> > VPII;
  44. typedef vector<pair<ll, ll> > VPLL;
  45.  
  46. template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
  47. template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
  48. template<class T1, class T2>
  49. ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
  50. template<class A, class B, class C> struct Triple { A first; B second; C third;
  51.   bool operator<(const Triple& t) const { if (st != t.st) return st < t.st; if (nd != t.nd) return nd < t.nd; return rd < t.rd; } };
  52. template<class T> void ResizeVec(T&, vector<int>) {}
  53. template<class T> void ResizeVec(vector<T>& vec, vector<int> sz) {
  54.   vec.resize(sz[0]); sz.erase(sz.begin()); if (sz.empty()) { return; }
  55.   for (T& v : vec) { ResizeVec(v, sz); }
  56. }
  57. typedef Triple<int, int, int> TIII;
  58. template<class A, class B, class C>
  59. ostream& operator<< (ostream &out, Triple<A, B, C> t) { return out << "(" << t.st << ", " << t.nd << ", " << t.rd << ")"; }
  60. template<class T> ostream& operator<<(ostream& out, vector<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  61. template<class T> ostream& operator<<(ostream& out, set<T> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  62. template<class L, class R> ostream& operator<<(ostream& out, map<L, R> vec) { out<<"("; for (auto& v: vec) out<<v<<", "; return out<<")"; }
  63.  
  64. typedef long double LD;
  65. const LD kEps = 1e-10;
  66. const LD kPi = 2 * acos(0);
  67. LD Sq(LD x) {
  68.   return x * x;
  69. }
  70. struct Point {
  71.   LD x, y;
  72.   Point() {}
  73.   Point(LD a, LD b) : x(a), y(b) {}
  74.   Point(const Point& a) : x(a.x), y(a.y) {}
  75.   void operator=(const Point& a) { x = a.x; y = a.y; }
  76.   Point operator+(const Point& a) const { Point p(x + a.x, y + a.y); return p; }
  77.   Point operator-(const Point& a) const { Point p(x - a.x, y - a.y); return p; }
  78.   Point operator*(LD a) const { Point p(x * a, y * a); return p; }
  79.   Point operator/(LD a) const { assert(abs(a) > kEps); Point p(x / a, y / a); return p; }
  80.   Point& operator+=(const Point& a) { x += a.x; y += a.y; return *this; }
  81.   Point& operator-=(const Point& a) { x -= a.x; y -= a.y; return *this; }
  82.   Point& operator*=(LD a) { x *= a; y *= a; return *this;}
  83.   Point& operator/=(LD a) { assert(abs(a) > kEps); x /= a; y /= a; return *this; }
  84.  
  85.   bool IsZero() const {
  86.     return abs(x) < kEps && abs(y) < kEps;
  87.   }
  88.   bool operator==(const Point& a) const {
  89.     return (*this - a).IsZero();
  90.   }
  91.   LD CrossProd(const Point& a) const {
  92.     return x * a.y - y * a.x;
  93.   }
  94.   LD CrossProd(Point a, Point b) const {
  95.     a -= *this;
  96.     b -= *this;
  97.     return a.CrossProd(b);
  98.   }
  99.   LD DotProd(const Point& a) const {
  100.     return x * a.x + y * a.y;
  101.   }
  102.   LD Norm() const {
  103.     return sqrt(Sq(x) + Sq(y));
  104.   }
  105.   void NormalizeSelf() {
  106.     *this /= Norm();
  107.   }
  108.   Point Normalize() {
  109.     Point res(*this);
  110.     res.NormalizeSelf();
  111.     return res;
  112.   }
  113.   LD Dist(const Point& a) const {
  114.     return (*this - a).Norm();
  115.   }
  116.   LD Angle() const {
  117.     return atan2(y, x);
  118.   }
  119.   void RotateSelf(LD angle) {
  120.     LD c = cos(angle);
  121.     LD s = sin(angle);
  122.     LD nx = x * c - y * s;
  123.     LD ny = y * c + x * s;
  124.     y = ny;
  125.     x = nx;
  126.   }
  127.   Point Rotate(LD angle) const {
  128.     Point res(*this);
  129.     res.RotateSelf(angle);
  130.     return res;
  131.   }
  132.   static bool LexCmp(const Point& a, const Point& b) {
  133.     if (abs(a.x - b.x) > kEps) {
  134.       return a.x < b.x;
  135.     }
  136.     return a.y < b.y;
  137.   }
  138.   LD SqNorm() {
  139.     return x * x + y * y;
  140.   }
  141.   friend ostream& operator<<(ostream& out, Point m);
  142. };
  143.  
  144. ostream& operator<<(ostream& out, Point p) {
  145.   out << "(" << p.x << ", " << p.y << ")";
  146.   return out;
  147. }
  148.  
  149. struct Circle {
  150.   Point center;
  151.   LD r;
  152.   Circle(LD x, LD y, LD rad) {
  153.     center = Point(x, y);
  154.     r = rad;
  155.   }
  156.   Circle(const Point& a, LD rad) : center(a), r(rad) {}
  157.   LD Area() const {
  158.     return kPi * Sq(r);
  159.   }
  160.   LD Perimeter() const {
  161.     return 2 * kPi * r;
  162.   }
  163.   LD Diameter() const {
  164.     return 2 * r;
  165.   }
  166.   Point RotateRightMost(LD ang) const {
  167.     return center + Point{r * cos(ang), r * sin(ang)};
  168.   }
  169.   bool operator==(const Circle& c) const {
  170.     return center == c.center && abs(r - c.r) < kEps;
  171.   }
  172. };
  173.  
  174. struct Line {
  175.   Point p[2];
  176.   bool is_seg;
  177.   Line(Point a, Point b, bool is_seg_ = false) {
  178.     p[0] = a;
  179.     p[1] = b;
  180.     is_seg = is_seg_;
  181.   }
  182.   Line() {
  183.   }
  184.   Point& operator[](int a) {
  185.     return p[a];
  186.   }
  187.   Point NormalVector() {
  188.     Point perp = p[1] - p[0];
  189.     perp.RotateSelf(kPi / 2);
  190.     perp.NormalizeSelf();
  191.     return perp;
  192.   }
  193.  
  194.   // (A, B, C) such that A^2 + B^2 = 1, (A, B) > (0, 0)
  195.   vector<LD> LineEqNormLD() { // seems ok
  196.     LD A = p[1].y - p[0].y;
  197.     LD B = p[0].x - p[1].x;
  198.     LD C = -(A * p[0].x + B * p[0].y);
  199.     assert(abs(A * p[1].x + B * p[1].y + C) < kEps);
  200.     LD norm = sqrt(Sq(A) + Sq(B));
  201.     vector<LD> res{A, B, C};
  202.     for (auto& x : res) { x /= norm; }
  203.     if (A < -kEps || (abs(A) < kEps && B < -kEps)) {
  204.       for (auto& x : res) { x *= -1; }
  205.     }
  206.     return res;
  207.   }
  208.  
  209.   // assumes that coordinates are integers!
  210.   vector<int> LineEqNormInt() { // seems ok
  211.     int A = round(p[1].y - p[0].y);
  212.     int B = round(p[0].x - p[1].x);
  213.     int C = -(A * p[0].x + B * p[0].y);
  214.     int gcd = abs(__gcd(A, __gcd(B, C)));
  215.     vector<int> res{A, B, C};
  216.     for (auto& x : res) { x /= gcd; }
  217.     if (A < 0 || (A == 0 && B < 0)) {
  218.       for (auto& x : res) { x *= -1; }
  219.     }
  220.     return res;
  221.   }
  222. };
  223.  
  224. struct Utils {
  225.   // 0, 1, 2 or 3 pts. In case of 3 pts it means they are equal
  226.   static vector<Point> InterCircleCircle(Circle a, Circle b) {
  227.     if (a.r + kEps < b.r) {
  228.       swap(a, b);
  229.     }
  230.     if (a == b) {
  231.       return vector<Point>{a.RotateRightMost(0), a.RotateRightMost(2 * kPi / 3),
  232.         a.RotateRightMost(4 * kPi / 3)};
  233.     }
  234.     Point diff = b.center - a.center;
  235.     LD dis = diff.Norm();
  236.     LD ang = diff.Angle();
  237.     LD longest = max(max(a.r, b.r), dis);
  238.     LD per = a.r + b.r + dis;
  239.     if (2 * longest > per + kEps) {
  240.       return vector<Point>();
  241.     }
  242.     if (abs(2 * longest - per) < 2 * kEps) {
  243.       return vector<Point>{a.RotateRightMost(ang)};
  244.     }
  245.     LD ang_dev = acos((Sq(a.r) + Sq(dis) - Sq(b.r)) / (2 * a.r * dis));
  246.     return vector<Point>{a.RotateRightMost(ang - ang_dev), a.RotateRightMost(ang + ang_dev)};
  247.   }
  248.  
  249.   static vector<Point> InterLineLine(Line& a, Line& b) { // working fine
  250.     Point vec_a = a[1] - a[0];
  251.     Point vec_b1 = b[1] - a[0];
  252.     Point vec_b0 = b[0] - a[0]; 
  253.     LD tr_area = vec_b1.CrossProd(vec_b0);
  254.     LD quad_area = vec_b1.CrossProd(vec_a) + vec_a.CrossProd(vec_b0);
  255.     if (abs(quad_area) < kEps) { // parallel or coinciding
  256.       if (PtBelongToLine(b, a[0])) {
  257.         return {a[0], a[1]};
  258.       } else {
  259.         return {};
  260.       }
  261.     }
  262.     return {a[0] + vec_a * (tr_area / quad_area)};
  263.   } 
  264.  
  265.   static Point ProjPointToLine(Point p, Line l) { ///Tested
  266.     Point diff = l[1] - l[0];
  267.     return l[0] + diff * (diff.DotProd(p - l[0]) / diff.DotProd(diff));
  268.   }
  269.  
  270.   static Point ReflectPtWRTLine(Point p, Line l) {
  271.     Point proj = ProjPointToLine(p, l);
  272.     return proj * 2 - p;
  273.   }
  274.  
  275.   static vector<Point> InterCircleLine(Circle c, Line l) { /// Tested here: http://c...content-available-to-author-only...s.com/gym/100554/submission/10197624
  276.     Point proj = ProjPointToLine(c.center, l);
  277.     LD dis_proj = c.center.Dist(proj);
  278.     if (dis_proj > c.r + kEps) { return vector<Point>(); }
  279.     LD a = sqrt(max((LD)0, Sq(c.r) - Sq(dis_proj)));
  280.     Point dir = l[1] - l[0];
  281.     LD dir_norm = dir.Norm();
  282.     vector<Point> cands{proj + dir * (a / dir_norm), proj - dir * (a / dir_norm)};
  283.     if (cands[0].Dist(cands[1]) < kEps) { return vector<Point>{proj}; }
  284.     return cands;
  285.   }
  286.  
  287.   static bool PtBelongToLine(Line l, Point p) {
  288.     return abs(l[0].CrossProd(l[1], p)) < kEps;
  289.   }
  290.  
  291.   static bool PtBelongToSeg(Line l, Point p) { // seems ok
  292.     return abs(p.Dist(l[0]) + p.Dist(l[1]) - l[0].Dist(l[1])) < kEps;
  293.   }
  294.  
  295.   static vector<Point> InterCircleSeg(Circle c, Line l) { //seems ok
  296.     vector<Point> from_line = InterCircleLine(c, l);
  297.     vector<Point> res;
  298.     for (auto p : from_line) {
  299.       if (PtBelongToSeg(l, p)) { res.PB(p); }
  300.     }
  301.     return res;
  302.   }
  303.  
  304.   static vector<Point> TangencyPtsToCircle(Circle c, Point p) { // seems ok
  305.     LD d = c.center.Dist(p);
  306.     if (d < c.r - kEps) { return {}; }
  307.     if (d < c.r + kEps) { return {p}; }
  308.     LD from_cent = (p - c.center).Angle();
  309.     LD ang_dev = acos(c.r / d);
  310.     return {c.RotateRightMost(from_cent - ang_dev), c.RotateRightMost(from_cent + ang_dev)};
  311.   }
  312.  
  313.   // outer and inner tangents tested only locally (however I believe that rigorously)
  314.   static vector<Line> OuterTangents(Circle c1, Circle c2) {
  315.     if (c1 == c2) { return {}; } // is it surely best choice?
  316.     if (c1.r < c2.r) { swap(c1, c2); }
  317.     if (c2.r + c1.center.Dist(c2.center) < c1.r - kEps) { return {}; }
  318.     if (abs(c1.r - c2.r) < kEps) {
  319.       Point diff = c2.center - c1.center;
  320.       Point R = diff.Rotate(kPi / 2) * (c1.r / diff.Norm()); 
  321.       return {{c1.center + R, c2.center + R}, {c1.center - R, c2.center - R}};
  322.     }
  323.     Point I = c1.center + (c2.center - c1.center) * (c1.r / (c1.r - c2.r)); 
  324.     if (c2.r + c1.center.Dist(c2.center) < c1.r + kEps) {
  325.       return {{I, I + (c2.center - c1.center).Rotate(kPi / 2)}};
  326.     }
  327.     vector<Point> to1 = TangencyPtsToCircle(c1, I);
  328.     vector<Point> to2 = TangencyPtsToCircle(c2, I);
  329.     vector<Line> res{{to1[0], to2[0]}, {to1[1], to2[1]}};
  330.     assert(Utils::PtBelongToLine(res[0], I));
  331.     assert(Utils::PtBelongToLine(res[1], I));
  332.     return res;
  333.   }
  334.  
  335.   // unfortunately big part of code is same as in previous function
  336.   // can be joined when putting appropriate signs in few places
  337.   // however those ifs differ a bit hence it may not be good idea
  338.   // to necessarily join them
  339.   static vector<Line> InnerTangents(Circle c1, Circle c2) {
  340.     if (c1 == c2) { return {}; } // this time surely best choice
  341.     if (c1.r < c2.r) { swap(c1, c2); }
  342.     LD d = c1.center.Dist(c2.center);
  343.     if (d < c1.r + c2.r - kEps) { return {}; }
  344.     Point I = c1.center + (c2.center - c1.center) * (c1.r / (c1.r + c2.r));
  345.     if (d < c1.r + c2.r + kEps) {
  346.       return {{I, I + (c2.center - c1.center).Rotate(kPi / 2)}};
  347.     }
  348.     vector<Point> to1 = TangencyPtsToCircle(c1, I);
  349.     vector<Point> to2 = TangencyPtsToCircle(c2, I);
  350.     vector<Line> res{{to1[0], to2[0]}, {to1[1], to2[1]}};
  351.     assert(Utils::PtBelongToLine(res[0], I));
  352.     assert(Utils::PtBelongToLine(res[1], I));
  353.     return res;
  354.   }
  355.  
  356.   static bool AreParallel(Line l1, Line l2) { // seems ok
  357.     return abs(l1[0].CrossProd(l2[0], l1[1]) - l1[0].CrossProd(l2[1], l1[1])) < kEps;
  358.   }
  359.  
  360.   // returns a vector of points such that their convex hull is intersection of those segments
  361.   // SZ(res) == 0 => empty intersection, SZ(res) == 1 => intersection is a point, SZ(res) == 2 => intersection is a segment
  362.   static vector<Point> InterSegs(Line l1, Line l2) { // seems ok
  363.     if (!Point::LexCmp(l1[0], l1[1])) { swap(l1[0], l1[1]); }
  364.     if (!Point::LexCmp(l2[0], l2[1])) { swap(l2[0], l2[1]); }
  365.     if (AreParallel(l1, l2)) {
  366.       if (!PtBelongToLine(l1, l2[0])) { return vector<Point>(); }
  367.       vector<Point> ends(2);
  368.       for (int tr = 0; tr < 2; tr++) {
  369.         if (Point::LexCmp(l1[tr], l2[tr]) ^ tr) {
  370.           ends[tr] = l2[tr];
  371.         } else {
  372.           ends[tr] = l1[tr];
  373.         }
  374.       }
  375.       if ((ends[1] - ends[0]).IsZero()) {
  376.         ends.pop_back();
  377.       }
  378.       if (SZ(ends) == 2 && Point::LexCmp(ends[1], ends[0])) { return vector<Point>(); }
  379.       return ends;
  380.     } else {
  381.       vector<Point> p = InterLineLine(l1, l2);
  382.       if (PtBelongToSeg(l1, p[0]) && PtBelongToSeg(l2, p[0])) { return p; }
  383.       return vector<Point>();
  384.     }
  385.   }
  386.  
  387.   static LD Angle(Point P, Point Q, Point R) { // angle PQR
  388.     LD ang2 = (P - Q).Angle();
  389.     LD ang1 = (R - Q).Angle();
  390.     LD ans = ang1 - ang2;
  391.     if (ans < kEps) {
  392.       ans += 2 * kPi;
  393.     }
  394.     return ans;
  395.   }
  396.  
  397.   // tested here: http://c...content-available-to-author-only...s.com/contest/600/submission/14961583
  398.   // DON'T change anything as this will lead to precision errors
  399.   // don't know why, but this is the only version which works precisely even for very mean cases
  400.   static LD DiskInterArea(Circle c1, Circle c2) { // tested here: http://o...content-available-to-author-only...s.info/~ejudge/team.cgi?contest_id=006254 problem I
  401.     if (c1.r < c2.r) {
  402.       swap(c1, c2);
  403.     }
  404.     LD d = c1.center.Dist(c2.center);
  405.     if (c1.r + c2.r < d + kEps) {
  406.       return 0;
  407.     }
  408.     if (c1.r - c2.r > d - kEps) {
  409.       return kPi * Sq(c2.r);
  410.     }
  411.     LD alfa = acos((Sq(d) + Sq(c1.r) - Sq(c2.r)) / (2 * d * c1.r));
  412.     LD beta = acos((Sq(d) + Sq(c2.r) - Sq(c1.r)) / (2 * d * c2.r));
  413.     return alfa * Sq(c1.r) + beta * Sq(c2.r) - sin(2 * alfa) * Sq(c1.r) / 2 - sin(2 * beta) * Sq(c2.r) / 2;
  414.   }
  415.  
  416.   static Line RadAxis(Circle c1, Circle c2) {
  417.     LD d = c1.center.Dist(c2.center);
  418.     LD a = (Sq(c1.r) - Sq(c2.r) + Sq(d)) / (2 * d);
  419.     Point Q = c1.center + (c2.center - c1.center) * (a / d);
  420.     Point R = Q + (c2.center - c1.center).Rotate(kPi / 2);
  421.     return Line(Q, R);
  422.   }
  423. };
  424. Point Rot(Point P) {
  425.   return {-P.y, P.x};
  426. }
  427.  
  428. LD Dis(Point A, Point B) {
  429.   return A.Dist(B);
  430. }
  431.  
  432. const int N = 1e5 + 5;
  433. Point flag[N];
  434.  
  435. int32_t main() {
  436.  
  437.   ios_base::sync_with_stdio(0);
  438.   cout << fixed << setprecision(10);
  439.   cerr << fixed << setprecision(10);
  440.   cin.tie(0);
  441.   //double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  442.  
  443.   int n;
  444.   cin>>n;
  445.   int res = n;
  446.   int x, y, A, B;
  447.   cin>>x>>y>>A>>B;
  448.   Point P = {(LD)x + A / 2, (LD)y - B / 2};
  449.   RE (i, n) {
  450.     int xf, yf;
  451.     cin>>xf>>yf;
  452.     flag[i] = {(LD)xf, (LD)yf};
  453.   }
  454.   REP (tr, 4) {
  455.     Point R{(LD)P.x - A / 2, (LD)P.y + B / 2};
  456.     Point Q{(LD)P.x + A / 2, (LD)P.y};
  457.  
  458.     int bil = 0;
  459.     Line hor{P, Q};
  460.     vector<pair<LD, int>> evs;
  461.     RE (i, n) {
  462.       int at_P = Dis(P, flag[i]) < Dis(P, R) + kEps;
  463.       int at_Q = Dis(Q, flag[i]) < Dis(Q, R) + kEps;
  464.       if (at_P == at_Q) {
  465.         if (at_P) {
  466.           bil++;
  467.         }
  468.         continue;
  469.       }
  470.  
  471.       Point midFR = (flag[i] + R) / 2;
  472.       Point dir = flag[i] - midFR;
  473.       dir = Rot(dir);
  474.       Line sym{midFR, midFR + dir};
  475.       vector<Point> inters = Utils::InterLineLine(sym, hor);
  476.       assert(SZ(inters) == 1);
  477.       Point inter = inters[0];
  478.       if (at_P) {
  479.         evs.PB({inter.x + kEps, -1});
  480.         bil++;
  481.       } else {
  482.         evs.PB({inter.x - kEps, 1});
  483.       }
  484.     }
  485.     sort(ALL(evs));
  486.     mini(res, bil);
  487.     for (auto ev : evs) {
  488.       bil += ev.nd;
  489.       mini(res, bil);
  490.     }
  491.  
  492.     P = Rot(P);
  493.     RE (i, n) {
  494.       flag[i] = Rot(flag[i]);
  495.     }
  496.     swap(A, B);
  497.   }
  498.   cout<<res<<endl;
  499.  
  500.  
  501.  
  502.   return 0;
  503. }
  504.  
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
5
-12 8 20 12
9 1
-9 -9
3 12
13 -4
-5 13
stdout
copy 
2
https://ideone.com/KkyBzb
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!