Youthful-Passion-Fruit-teambook
This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub AlexanderNekrasov/Youthful-Passion-Fruit-teambook
verify/geometry/igor-tests/19.test.cpp
- View this file on GitHub
- Last update: 2024-08-11 10:07:38+00:00
- Problem: https://judge.yosupo.jp/problem/aplusb
Depends on
- contest/template.cpp
- geometry/HalfPlaneIntersection.cpp
- geometry/Intersections.cpp
- geometry/IsHpiEmpty.cpp
- geometry/Line.cpp
- geometry/Point.cpp
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/IsHpiEmpty.cpp"
#include "../../../geometry/HalfPlaneIntersection.cpp"
void test() {
int N = 10;
int C = 10;
auto get = [&](int l, int r) -> int {
return (ull)rnd() % (r - l + 1) + l;
};
auto getPoint = [&]() -> point {
return {get(-C, C), get(-C, C)};
};
for (int test_id = 0;test_id<10000; ++test_id) {
int n = get(1, N);
vector<line> lines(n);
for (int i = 0; i < n; ++i) {
point a = getPoint();
point b = getPoint();
while (a == b) {
b = getPoint();
}
lines[i] = getln(a, b);
}
// cerr << "n = " << n << endl;
// cerr << "lines = " << endl;
// for (auto [a, b, c] : lines) {
// cerr << "x * " << a << " + y * " << b << " + " << c << " = 0"
// << endl;
// }
const ld C = 1e9;
vector<point> box = {{-C, -C}, {C, -C}, {C, C}, {-C, C}};
for (int i = 0; i < 4; ++i) {
lines.push_back(getln(box[i], box[(i + 1) % 4]));
}
bool ans = hpi(lines).empty();
lines.resize(n);
bool out = isHpiEmpty(lines);
if (ans == 0 && out == 1) {
cerr << "WA isHpiEmpty " << test_id << endl;
cerr << "n = " << n << endl;
cerr << "lines = " << endl;
for (auto [a, b, c] : lines) {
cerr << "x * " << a << " + y * " << b << " + " << c
<< " = 0" << endl;
}
cerr << "ans = " << ans << endl;
cerr << "out = " << out << endl;
exit(1);
}
cerr << "OK " << test_id << " ans = " << ans << 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/19.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/19.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/IsHpiEmpty.cpp"
/**
* Author: Igor Markelov
* Date: 2022-11-18
* Description: Determines is half plane intersectinos.
* Time: O(n) (expected)
*/
// all lines must be normed!!!!!, sign > 0
bool isHpiEmpty(vector<line> lines) {
// return hpi(lines).empty();
// overflow/precision problems?
shuffle(all(lines), rnd);
const ld C = 1e9;
point ans(C, C);
vector<point> box = {{-C, -C}, {C, -C}, {C, C}, {-C, C}};
for (int i = 0; i < 4; ++i)
lines.push_back(getln(box[i], box[(i + 1) % 4]));
int n = lines.size();
for (int i = n - 4; i >= 0; --i) {
if (lines[i].isIn(ans))
continue;
point up(0, C + 1), down(0, -C - 1), pi = {lines[i].b, -lines[i].a};
for (int j = i + 1; j < n; ++j) {
if (lines[i] == lines[j])
continue;
point p, pj = {lines[j].b, -lines[j].a};
if (!intersect(lines[i], lines[j], p)) {
if (sign(pi * pj) != -1)
continue;
if (sign(lines[i].c + lines[j].c) *
(!sign(pi.y) ? sign(pi.x) : -1) ==
1)
return true;
} else {
if ((!sign(pi.y) ? sign(pi.x) : sign(pi.y)) * (sign(pi % pj)) ==
1)
chkmin(up, p);
else
chkmax(down, p);
}
}
if ((ans = up) < down)
return true;
}
// for (int i = 0; i < n; ++i) {
// assert(lines[i].eval(ans) < EPS);
// }
return false;
}
#line 1 "geometry/HalfPlaneIntersection.cpp"
/**
* Author: Igor Markelov (stole from Red Panda teambook)
* Date: 2022-11-05
* Description: Find the intersection of the half planes.
* Time: O(n \log(n))
*/
vec getPoint(line l) { return {-l.b, l.a}; }
bool bad(line a, line b, line c) {
point x;
assert(intersect(b, c, x) == 1);
return a.eval(x) < 0;
}
// Do not forget about the bounding box
vector<point> hpi(vector<line> lines) {
sort(all(lines), [](line al, line bl) -> bool {
point a = getPoint(al);
point b = getPoint(bl);
if (half(a) != half(b)) {
return half(a) < half(b);
}
return a % b > 0;
});
vector<pair<line, int>> st;
for (int it = 0; it < 2; it++) {
for (int i = 0; i < (int)lines.size(); i++) {
bool flag = false;
while (!st.empty()) {
if (len(getPoint(st.back().first) - getPoint(lines[i])) < EPS) {
if (lines[i].c >= st.back().first.c) {
flag = true;
break;
} else {
st.pop_back();
}
} else if (getPoint(st.back().first) % getPoint(lines[i]) < EPS / 2) {
return {};
} else if (st.size() >= 2 &&
bad(st[st.size() - 2].first, st[st.size() - 1].first,
lines[i])) {
st.pop_back();
} else {
break;
}
}
if (!flag)
st.push_back({lines[i], i});
}
}
vector<int> en(lines.size(), -1);
vector<point> ans;
for (int i = 0; i < (int)st.size(); i++) {
if (en[st[i].second] == -1) {
en[st[i].second] = i;
continue;
}
for (int j = en[st[i].second]; j < i; j++) {
point I;
assert(intersect(st[j].first, st[j + 1].first, I) == 1);
ans.push_back(I);
}
break;
}
return ans;
}
#line 11 "verify/geometry/igor-tests/19.test.cpp"
void test() {
int N = 10;
int C = 10;
auto get = [&](int l, int r) -> int {
return (ull)rnd() % (r - l + 1) + l;
};
auto getPoint = [&]() -> point {
return {get(-C, C), get(-C, C)};
};
for (int test_id = 0;test_id<10000; ++test_id) {
int n = get(1, N);
vector<line> lines(n);
for (int i = 0; i < n; ++i) {
point a = getPoint();
point b = getPoint();
while (a == b) {
b = getPoint();
}
lines[i] = getln(a, b);
}
// cerr << "n = " << n << endl;
// cerr << "lines = " << endl;
// for (auto [a, b, c] : lines) {
// cerr << "x * " << a << " + y * " << b << " + " << c << " = 0"
// << endl;
// }
const ld C = 1e9;
vector<point> box = {{-C, -C}, {C, -C}, {C, C}, {-C, C}};
for (int i = 0; i < 4; ++i) {
lines.push_back(getln(box[i], box[(i + 1) % 4]));
}
bool ans = hpi(lines).empty();
lines.resize(n);
bool out = isHpiEmpty(lines);
if (ans == 0 && out == 1) {
cerr << "WA isHpiEmpty " << test_id << endl;
cerr << "n = " << n << endl;
cerr << "lines = " << endl;
for (auto [a, b, c] : lines) {
cerr << "x * " << a << " + y * " << b << " + " << c
<< " = 0" << endl;
}
cerr << "ans = " << ans << endl;
cerr << "out = " << out << endl;
exit(1);
}
cerr << "OK " << test_id << " ans = " << ans << endl;
}
}
int main() {
int a, b;
cin >> a >> b;
if (a == 1234 && b == 5678) test();
cout << a + b << endl;
}