verify/geometry/igor-tests/18.test.cpp

View this file on GitHub
Last update: 2024-08-11 09:50:12+00:00
Problem: https://judge.yosupo.jp/problem/aplusb

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#define main main2
#include "../../../contest/template.cpp"
#undef main

#include "../../../geometry/Point.cpp"
#include "../../../geometry/Line.cpp"
#include "../../../geometry/Intersections.cpp"
#include "../../../geometry/IsInPolygon.cpp"
#include "../../../geometry/TangentsAlex.cpp"
#include "../../../geometry/Hull.cpp"

void test() {
    int N = 100000;
    int C = 1e9;
    int Q = 100;
    auto get = [&] (int l, int r) -> int {
      return (ull)rnd() % (r - l + 1) + l;
    };
    auto stupidTangents = [&] (vector<point>& p, point& a) {
      auto cmp = [&](point& lhs, point& rhs) -> bool {
        return sign((lhs - a) % (rhs - a)) > 0;
      };
      int posL = min_element(all(p), cmp) - p.begin();
      int posR = max_element(all(p), cmp) - p.begin();
      return mp(posL, posR);
    };
    for (int test_id = 0; test_id < 50; ++test_id) {
      int n = get(1, N);
      vector<point> p(n);
      for (int i = 0; i < n; ++i) {
        p[i] =vec{(ld)get(-C, C), (ld)get(-C, C)};
      }
      p = hull(p);
      n = p.size();
      for (int i = 0; i < Q; ++i) {
        point a{(ld)-C, (ld)C};
        if (p.size() >= 3) {
          if(isInConvex(p, a) != isIn(p, a)) {
            cerr << "WA convex " << test_id << " " << i << endl;
            cerr << "n = " << n << endl;
            cerr << "p = " << endl;
            for (auto [x, y] : p) {
              cerr << "(" << x << ", " << y << ")" << endl;
            }
            cerr << "a = " << endl;
            cerr << "(" << a.x << " " << a.y << ")" << endl;
            cerr << "ans = " << isIn(p, a) << endl;
            cerr << "out = " << isInConvex(p, a) << endl;
            exit(1);
          }
        }
        if (isIn(p, a)) continue;
        auto ans = stupidTangents(p, a);
        auto out = tangents_alex(p, a);
        bool ok = true;
        if (sign((p[ans.first] - a) % (p[out.first] - a)) != 0) {
          ok = false;
        } else if (sign((p[ans.second] - a) % (p[out.second] - a)) != 0) {
          ok = false;
        }
        if (!ok) {
          cerr << "WA tangents " << test_id << " " << i << endl;
          cerr << "n = " << n << endl;
          cerr << "p = " << endl;
          for (auto [x, y] : p) {
            cerr << "(" << x << ", " << y << ")" << endl;
          }
          cerr << "a = " << endl;
          cerr << "(" << a.x << " " << a.y << ")" << endl;
          cerr << "ans = " << ans.first << " " << ans.second << endl;
          cerr << "out = " << out.first << " " << out.second << endl;
          exit(1);
        }
      }
      cerr << "OK " << test_id << endl;
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    if (a == 1234 && b == 5678) test();
    cout << a + b << endl;
}

#line 1 "verify/geometry/igor-tests/18.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#define main main2
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define pbc push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define vin(v) for (auto &el : a) cin >> el

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 &y) {
    if (y < x) {
        x = y;
    }
}

template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 &y) {
    if (x < y) {
        x = y;
    }
}

void solve() {
    
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cout.precision(20), cout.setf(ios::fixed);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}
#line 4 "verify/geometry/igor-tests/18.test.cpp"
#undef main

#line 1 "geometry/Point.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: struct Point
 */

const ld EPS = 1e-7;

ld sq(ld x) {
    return x * x;
}

int sign(ld x) {
    if (x < -EPS) {
        return -1;
    }
    if (x > EPS) {
        return 1;
    }
    return 0;
}

#define vec point
struct point {//% - cross, * - dot
    ld x, y;
    auto operator<=>(const point&) const = default;
};
ld operator*(const point &a, const point &b) {
    return a.x * b.x + a.y * b.y;
}
ld operator%(const point &a, const point &b) {
    return a.x * b.y - a.y * b.x;
}
point operator-(const point &a, const point &b) {
    return {a.x - b.x, a.y - b.y};
}
point operator+(const point &a, const point &b) {
    return {a.x + b.x, a.y + b.y};
}
point operator*(const point &a, ld b) {
    return {a.x * b, a.y * b};
}
point operator/(const point &a, ld b) {
    return {a.x / b, a.y / b};
}
bool operator<(const point &a, const point &b)  {
    if (sign(a.y - b.y) != 0) {
        return a.y < b.y;
    } else if (sign(a.x - b.x) != 0) {
        return a.x < b.x;
    }
    return 0;
}
ld len2(const point &a) {
    return sq(a.x) + sq(a.y);
}
ld len(const point &a) {
    return sqrt(len2(a));
}
point norm(point a) {
    return a / len(a);
}
int half(point a) {
    return (sign(a.y) == -1 || (sign(a.y) ==0 && a.x < 0));
}
point ort(point a) {
    return {-a.y, a.x};
}
point turn(point a, ld ang) {
    return {a.x * cos(ang) - a.y * sin(ang), a.x * sin(ang) + a.y * cos(ang)};
}
ld getAngle(point &a, point &b) {
    return atan2(a % b, a * b);
}
bool cmpHalf(const point &a, const point &b) {
    if (half(a) != half(b)) {
        return half(b);
    } else {
        int sgn = sign(a % b);
        if (!sgn) {
            return len2(a) < len2(b);
        } else {
            return sgn == 1;
        }
    }
}
#line 1 "geometry/Line.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: struct Line
 */

struct line {
    ld a, b, c;
    void norm() {
        // for half planes
        ld d = len({a, b});
        assert(sign(d) > 0);
        a /= d;
        b /= d;
        c /= d;
    }
    ld eval(point p) const { return a * p.x + b * p.y + c; }
    bool isIn(point p) const { return sign(eval(p)) >= 0; }
    bool operator==(const line &other) const {
        return sign(a * other.b - b * other.a) == 0 &&
               sign(a * other.c - c * other.a) == 0 &&
               sign(b * other.c - c * other.b) == 0;
    }
};
line getln(point a, point b) {
    line res;
    res.a = a.y - b.y;
    res.b = b.x - a.x;
    res.c = -(res.a * a.x + res.b * a.y);
    res.norm();
    return res;
}
#line 1 "geometry/Intersections.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: Geometry intersections
 */

bool isCrossed(ld lx, ld rx, ld ly, ld ry) {
    if (lx > rx)
        swap(lx, rx);
    if (ly > ry)
        swap(ly, ry);
    return sign(min(rx, ry) - max(lx, ly)) >= 0;
}

// if two segments [a, b] and [c, d] has AT LEAST one common point -> true
bool intersects(const point &a, const point &b, const point &c, const point &d) {
    if (!isCrossed(a.x, b.x, c.x, d.x))
        return false;
    if (!isCrossed(a.y, b.y, c.y, d.y))
        return false;
    if (sign((b - a) % (c - a)) * sign((b - a) % (d - a)) == 1) return 0;
    if (sign((d - c) % (a - c)) * sign((d - c) % (b - c)) == 1) return 0;
    return 1;
}
//intersecting lines
bool intersect(line l, line m, point &I) {
    ld d = l.b * m.a - m.b * l.a;
    if (sign(d) == 0) {
        return false;
    }
    ld dx = m.b * l.c - m.c * l.b;
    ld dy = m.c * l.a - l.c * m.a;
    I = {dx / d, dy / d};
    return true;
}
//intersecting circles
int intersect(point o1, ld r1, point o2, ld r2, point &i1, point &i2) {
    if (r1 < r2) {
        swap(o1, o2);
        swap(r1, r2);
    }
    if (sign(r1 - r2) == 0 && len2(o2 - o1) < EPS) {
        return 3;
    }
    ld ln = len(o1 - o2);
    if (sign(ln - r1 - r2) == 1 || sign(r1 - ln - r2) == 1) {
        return 0;
    }
    ld d = (sq(r1) - sq(r2) + sq(ln)) / 2 / ln;
    vec v = norm(o2 - o1);
    point a = o1 + v * d;
    if (sign(ln - r1 - r2) == 0 || sign(ln + r2 - r1) == 0) {
        i1 = a;
        return 1;
    }
    v = ort(v) * sqrt(sq(r1) - sq(d));
    i1 = a + v;
    i2 = a - v;
    return 2;
}
//intersecting line and circle, line should be normed
int intersect(point o, ld r, line l, point &i1, point &i2) {
    ld len = abs(l.eval(o));
    int sgn = sign(len - r);
    if (sgn == 1) {
        return 0;
    }
    vec v = norm(vec{l.a, l.b}) * len;
    if (sign(l.eval(o + v)) != 0) {
        v = vec{0, 0} - v;
    }
    point a = o + v;
    if (sgn == 0) {
        i1 = a;
        return 1;
    }
    v = norm({-l.b, l.a}) * sqrt(sq(r) - sq(len));
    i1 = a + v;
    i2 = a - v;
    return 2;
}
#line 1 "geometry/IsInPolygon.cpp"
/**
 * Author: Igor Markelov
 * Date: 2022-11-18
 * Description: Is in polygon functions
 */

bool isOnSegment(point &a, point &b, point &x) {
    if (sign(len2(a - b)) == 0) {
        return sign(len(a - x)) == 0;
    }
    return sign((b - a) % (x - a)) == 0 && sign((b - x) * (a - x)) <= 0;
    // optional (slower, but works better if there are some precision
    // problems) return sign((b - a).len() - (x - a).len() - (x - b).len())
    // == 0;
}

int isIn(vector<point> &p, point &a) {
    int n = p.size();
    // depends on limitations(2*MAXC + 228)
    point b = a + point{2e9 + 228, 1};
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        point x = p[i];
        point y = p[i + 1 < n ? i + 1 : 0];
        if (isOnSegment(x, y, a)) {
            // depends on the problem statement
            return 1;
        }
        cnt += intersects(x, y, a, b);
    }
    return 2 * (cnt % 2 == 1);
    /*optional (atan2 is VERY SLOW)!
    ld ans = 0;
    int n = p.size();
    for (int i = 0; i < n; ++i) {
      Point x = p[i];
      Point y = p[i + 1 < n ? i + 1 : 0];
      if (isOnSegment(x, y, a)) {
        // depends on the problem statement
        return true;
      }
      x = x - a;
      y = y - a;
      ans += atan2(x ^ y, x * y);
    }
    return abs(ans) > 1;*/
}

bool isInTriangle(point &a, point &b, point &c, point &x) {
    return sign((b - a) % (x - a)) >= 0 && sign((c - b) % (x - b)) >= 0 &&
           sign((a - c) % (x - c)) >= 0;
}

// points should be in the counterclockwise order
bool isInConvex(vector<point> &p, point &a) {
    int n = p.size();
    assert(n >= 3);
    // assert(isConvex(p));
    // assert(isCounterclockwise(p));
    if (sign((p[1] - p[0]) % (a - p[0])) < 0)
        return 0;
    if (sign((p[n - 1] - p[0]) % (a - p[0])) > 0)
        return 0;
    int pos = lower_bound(p.begin() + 2, p.end(), a,
                          [&](point a, point b) -> bool {
                              return sign((a - p[0]) % (b - p[0])) > 0;
                          }) -
              p.begin();
    assert(pos > 1 && pos < n);
    return isInTriangle(p[0], p[pos - 1], p[pos], a);
}
#line 1 "geometry/TangentsAlex.cpp"
/**
 * Author: Igor Markelov
 * Date: 2022-11-18
 * Description: Find both tangets to the convex polygon. \\
 * (Zakaldovany algos mozhet sgonyat za pivom tak zhe).
 * Time: O(\log(n))
 */

pair<int, int> tangents_alex(vector<point> &p, point &a) {
    int n = p.size();
    int l = __lg(n);
    auto findWithSign = [&](int val) {
        int i = 0;
        for (int k = l; k >= 0; --k) {
            int i1 = (i - (1 << k) + n) % n;
            int i2 = (i + (1 << k)) % n;
            if (sign((p[i1] - a) % (p[i] - a)) == val)
                i = i1;
            if (sign((p[i2] - a) % (p[i] - a)) == val)
                i = i2;
        }
        return i;
    };
    return {findWithSign(1), findWithSign(-1)};
}
#line 1 "geometry/Hull.cpp"
/**
 * Author: alexxela12345,daubi,talant
 * Date: 2024-08-03
 * Description: Polygon functions
 */

vector<point> hull(vector<point> p, bool need_all=false) {
   sort(all(p));
   p.erase(unique(all(p)), end(p));
   int n = p.size(), k = 0;
   if (n <= 2) return p;
   vector<point> ch(2 * n);
   ld th = need_all ? -EPS : +EPS; // 0 : 1 if int
   for (int i = 0; i < n; ch[k++] = p[i++]) {
     while (k >= 2 && (ch[k - 1] - ch[k - 2]) % (p[i] - ch[k - 1]) < th) --k;
   }
   for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]) {
     while (k >= t && (ch[k - 1] - ch[k - 2]) % (p[i] - ch[k - 1]) < th) --k;
   }
   ch.resize(k - 1);
   return ch;
 }
#line 12 "verify/geometry/igor-tests/18.test.cpp"

void test() {
    int N = 100000;
    int C = 1e9;
    int Q = 100;
    auto get = [&] (int l, int r) -> int {
      return (ull)rnd() % (r - l + 1) + l;
    };
    auto stupidTangents = [&] (vector<point>& p, point& a) {
      auto cmp = [&](point& lhs, point& rhs) -> bool {
        return sign((lhs - a) % (rhs - a)) > 0;
      };
      int posL = min_element(all(p), cmp) - p.begin();
      int posR = max_element(all(p), cmp) - p.begin();
      return mp(posL, posR);
    };
    for (int test_id = 0; test_id < 50; ++test_id) {
      int n = get(1, N);
      vector<point> p(n);
      for (int i = 0; i < n; ++i) {
        p[i] =vec{(ld)get(-C, C), (ld)get(-C, C)};
      }
      p = hull(p);
      n = p.size();
      for (int i = 0; i < Q; ++i) {
        point a{(ld)-C, (ld)C};
        if (p.size() >= 3) {
          if(isInConvex(p, a) != isIn(p, a)) {
            cerr << "WA convex " << test_id << " " << i << endl;
            cerr << "n = " << n << endl;
            cerr << "p = " << endl;
            for (auto [x, y] : p) {
              cerr << "(" << x << ", " << y << ")" << endl;
            }
            cerr << "a = " << endl;
            cerr << "(" << a.x << " " << a.y << ")" << endl;
            cerr << "ans = " << isIn(p, a) << endl;
            cerr << "out = " << isInConvex(p, a) << endl;
            exit(1);
          }
        }
        if (isIn(p, a)) continue;
        auto ans = stupidTangents(p, a);
        auto out = tangents_alex(p, a);
        bool ok = true;
        if (sign((p[ans.first] - a) % (p[out.first] - a)) != 0) {
          ok = false;
        } else if (sign((p[ans.second] - a) % (p[out.second] - a)) != 0) {
          ok = false;
        }
        if (!ok) {
          cerr << "WA tangents " << test_id << " " << i << endl;
          cerr << "n = " << n << endl;
          cerr << "p = " << endl;
          for (auto [x, y] : p) {
            cerr << "(" << x << ", " << y << ")" << endl;
          }
          cerr << "a = " << endl;
          cerr << "(" << a.x << " " << a.y << ")" << endl;
          cerr << "ans = " << ans.first << " " << ans.second << endl;
          cerr << "out = " << out.first << " " << out.second << endl;
          exit(1);
        }
      }
      cerr << "OK " << test_id << endl;
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    if (a == 1234 && b == 5678) test();
    cout << a + b << endl;
}