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/include-all.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/Hull.cpp
- geometry/Intersections.cpp
- geometry/IsHpiEmpty.cpp
- geometry/IsInPolygon.cpp
- geometry/Line.cpp
- geometry/Point.cpp
- geometry/Tangents.cpp
- verify/geometry/igor-tests/01.cpp
- verify/geometry/igor-tests/02.cpp
- verify/geometry/igor-tests/03.cpp
- verify/geometry/igor-tests/04.cpp
- verify/geometry/igor-tests/05.cpp
- verify/geometry/igor-tests/06.cpp
- verify/geometry/igor-tests/07.cpp
- verify/geometry/igor-tests/08.cpp
- verify/geometry/igor-tests/09.cpp
- verify/geometry/igor-tests/10.cpp
- verify/geometry/igor-tests/11.cpp
- verify/geometry/igor-tests/12.cpp
- verify/geometry/igor-tests/13.cpp
- verify/geometry/igor-tests/14.cpp
- verify/geometry/igor-tests/15.cpp
- verify/geometry/igor-tests/16.cpp
- verify/geometry/igor-tests/17.cpp
- verify/geometry/igor-tests/20.cpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#define main main2
#include "../../../contest/template.cpp"
#undef main
namespace a0 {
#include "01.cpp"
};
namespace a1 {
#include "02.cpp"
};
namespace a2 {
#include "03.cpp"
};
namespace a3 {
#include "04.cpp"
};
namespace a4 {
#include "05.cpp"
};
namespace a5 {
#include "06.cpp"
};
namespace a6 {
#include "07.cpp"
};
namespace a7 {
#include "08.cpp"
};
namespace a8{
#include "09.cpp"
};
namespace a9 {
#include "10.cpp"
};
namespace a10 {
#include "11.cpp"
};
namespace a11 {
#include "12.cpp"
};
namespace a12 {
#include "13.cpp"
};
namespace a13 {
#include "14.cpp"
};
namespace a14 {
#include "15.cpp"
};
namespace a15 {
#include "16.cpp"
};
namespace a16 {
#include "17.cpp"
};
namespace a17 {
#include "20.cpp"
};
void test() {
}
int main() {
int a, b;
cin >> a >> b;
if (a == 1234 && b == 5678) test();
cout << a + b << endl;
}#line 1 "verify/geometry/igor-tests/include-all.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/include-all.test.cpp"
#undef main
namespace a0 {
#line 1 "verify/geometry/igor-tests/01.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 A - Площадь треугольника
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/01.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 8 "verify/geometry/igor-tests/01.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point a, b, c;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
cout << abs((b - a) % (c - a)) / 2 << endl;
}
#line 8 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a1 {
#line 1 "verify/geometry/igor-tests/02.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 B - Угол между векторами
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/02.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 8 "verify/geometry/igor-tests/02.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
vec a, b;
cin >> a.x >> a.y >> b.x >> b.y;
cout << abs(getAngle(a, b)) << endl;
}
#line 11 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a2 {
#line 1 "verify/geometry/igor-tests/03.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 C - Точка в углу
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/03.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 8 "verify/geometry/igor-tests/03.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
vec a, o, b, p;
cin >> a.x >> a.y >> o.x >> o.y >> b.x >> b.y >> p.x >> p.y;
a = a - o;
b = b - o;
if (sign(a % b) <= 0) {
swap(a, b);
}
p = p - o;
bool ok = true;
if (sign(a % b) == 1) {
ok = sign(a % p) >= 0 && sign(p % b) >= 0;
} else {
ok = !(sign(a % p) < 0 && sign(p % b) < 0);
}
if (ok) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
#line 14 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a3 {
#line 1 "verify/geometry/igor-tests/04.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 D - Пересечение отрезков
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/04.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 10 "verify/geometry/igor-tests/04.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
vec a, b, c, d;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
if (intersects(a, b, c, d)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
#line 17 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a4 {
#line 1 "verify/geometry/igor-tests/05.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 E - Расстояние от точки до прямой
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 6 "verify/geometry/igor-tests/05.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 10 "verify/geometry/igor-tests/05.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point p;
cin >> p.x >> p.y;
line l;
cin >> l.a >> l.b >> l.c;
l.norm();
cout << abs(l.eval(p)) << endl;
}
#line 20 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a5 {
#line 1 "verify/geometry/igor-tests/06.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 F - Пересечение прямых
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 6 "verify/geometry/igor-tests/06.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 11 "verify/geometry/igor-tests/06.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
vec a, b, c, d;
line l, m;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
l = getln(a, b);
m = getln(c, d);
vec ans;
if (intersect(l, m, ans)) {
cout << 1 << " " << ans.x << " " << ans.y << endl;
} else if (l == m) {
cout << 2 << endl;
} else {
cout << 0 << endl;
}
}
#line 23 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a6 {
#line 1 "verify/geometry/igor-tests/07.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 G - Пусти козла в огород - 1
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 6 "verify/geometry/igor-tests/07.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 11 "verify/geometry/igor-tests/07.cpp"
const ld PI = acos(-1);
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point a, b, c;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
auto calc = [](vec lhs, vec rhs) -> ld {
ld sgn = sign(lhs % rhs);
if (!sgn) {
return 180;
}
if (sgn < 0) {
swap(lhs, rhs);
}
return atan2(lhs % rhs, lhs * rhs) / (2 * PI) * 360;
};
cout << max({calc(b - a, c - a), calc(c - b, a - b), calc(a - c, b - c)}) << endl;
}
#line 26 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a7 {
#line 1 "verify/geometry/igor-tests/08.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 H - Биссектриса
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 6 "verify/geometry/igor-tests/08.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 10 "verify/geometry/igor-tests/08.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point x, y, z;
cin >> x.x >> x.y >> y.x >> y.y >> z.x >> z.y;
y = norm(y - x);
z = norm(z - x);
line l = getln(x, x + y + z);
cout << l.a << " " << l.b << " " << l.c << endl;
}
#line 29 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a8{
#line 1 "verify/geometry/igor-tests/09.cpp"
// Yandex Algo 2023-2024. C. Геометрия 1 I - Пусти козла в огород - 4
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55061
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 6 "verify/geometry/igor-tests/09.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 11 "verify/geometry/igor-tests/09.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point a, b, c;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
vec v1, v2;
v1 = norm(b - a);
v2 = norm(c - a);
line l = getln(a, a + v1 + v2);
v1 = norm(a - b);
v2 = norm(c - b);
line m = getln(b, b + v1 + v2);
point ans;
if (intersect(l, m, ans)) {
cout << ans.x << " " << ans.y << endl;
} else {
assert(false);
}
}
#line 32 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a9 {
#line 1 "verify/geometry/igor-tests/10.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 A - Касательные к окружности
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/10.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/Tangents.cpp"
/**
* Author: Igor Markelov
* Date: 2022-11-18
* Description: Tangents to circles.
*/
// tangents from point to circle
int tangents(point &o, ld r, point &p, point &i1, point &i2) {
ld ln = len(o - p);
int sgn = sign(ln - r);
if (sgn == -1) {
return 0;
} else if (sgn == 0) {
i1 = p;
return 1;
} else {
ld x = sq(r) / ln;
vec v = norm(p - o) * x;
point a = o + v;
v = ort(norm(p - o)) * sqrt(sq(r) - sq(x));
i1 = a + v;
i2 = a - v;
return 2;
}
}
void _tangents(point c, ld r1, ld r2, vector<line> &ans) {
ld r = r2 - r1;
ld z = sq(c.x) + sq(c.y);
ld d = z - sq(r);
if (sign(d) == -1)
return;
d = sqrt(abs(d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back(l);
}
// tangents between two circles
vector<line> tangents(point o1, ld r1, point o2, ld r2) {
vector<line> ans;
for (int i = -1; i <= 1; i += 2)
for (int j = -1; j <= 1; j += 2)
_tangents(o2 - o1, r1 * i, r2 * j, ans);
for (int i = 0; i < (int)ans.size(); ++i)
ans[i].c -= ans[i].a * o1.x + ans[i].b * o1.y;
return ans;
}
#line 10 "verify/geometry/igor-tests/10.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point o, p;
ld r;
cin >> o.x >> o.y >> r >> p.x >> p.y;
point I1, I2;
int ans = tangents(o, r, p, I1, I2);
if (!ans) {
cout << ans << endl;
} else if (ans == 1) {
cout << ans << "\n" << I1.x << " " << I1.y << endl;
} else if (ans == 2) {
cout << ans << "\n" << I1.x << " " << I1.y << "\n" << I2.x << " " << I2.y << endl;
}
}
#line 35 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a10 {
#line 1 "verify/geometry/igor-tests/11.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 B - Пересекаем окружности
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/11.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/Tangents.cpp"
/**
* Author: Igor Markelov
* Date: 2022-11-18
* Description: Tangents to circles.
*/
// tangents from point to circle
int tangents(point &o, ld r, point &p, point &i1, point &i2) {
ld ln = len(o - p);
int sgn = sign(ln - r);
if (sgn == -1) {
return 0;
} else if (sgn == 0) {
i1 = p;
return 1;
} else {
ld x = sq(r) / ln;
vec v = norm(p - o) * x;
point a = o + v;
v = ort(norm(p - o)) * sqrt(sq(r) - sq(x));
i1 = a + v;
i2 = a - v;
return 2;
}
}
void _tangents(point c, ld r1, ld r2, vector<line> &ans) {
ld r = r2 - r1;
ld z = sq(c.x) + sq(c.y);
ld d = z - sq(r);
if (sign(d) == -1)
return;
d = sqrt(abs(d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back(l);
}
// tangents between two circles
vector<line> tangents(point o1, ld r1, point o2, ld r2) {
vector<line> ans;
for (int i = -1; i <= 1; i += 2)
for (int j = -1; j <= 1; j += 2)
_tangents(o2 - o1, r1 * i, r2 * j, ans);
for (int i = 0; i < (int)ans.size(); ++i)
ans[i].c -= ans[i].a * o1.x + ans[i].b * o1.y;
return ans;
}
#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 11 "verify/geometry/igor-tests/11.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
int t;
cin >> t;
while (t--) {
point o1, o2;
ld r1, r2;
cin >> o1.x >> o1.y >> r1 >> o2.x >> o2.y >> r2;
point I1, I2;
int ans = intersect(o1, r1, o2, r2, I1, I2);
if (!ans || ans == 3) {
cout << ans << endl;
} else if (ans == 1) {
cout << ans << "\n" << I1.x << " " << I1.y << endl;
} else if (ans == 2) {
point fans = (I1 + I2) / 2;
cout << ans << "\n"
<< fans.x << " " << fans.y << "\n"
<< len(o1 - fans) << " " << len(I1 - fans) << "\n"
<< I1.x << " " << I1.y << "\n"
<< I2.x << " " << I2.y << endl;
}
}
}
#line 38 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a11 {
#line 1 "verify/geometry/igor-tests/12.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 C - Прямая и окружность
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/12.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/Tangents.cpp"
/**
* Author: Igor Markelov
* Date: 2022-11-18
* Description: Tangents to circles.
*/
// tangents from point to circle
int tangents(point &o, ld r, point &p, point &i1, point &i2) {
ld ln = len(o - p);
int sgn = sign(ln - r);
if (sgn == -1) {
return 0;
} else if (sgn == 0) {
i1 = p;
return 1;
} else {
ld x = sq(r) / ln;
vec v = norm(p - o) * x;
point a = o + v;
v = ort(norm(p - o)) * sqrt(sq(r) - sq(x));
i1 = a + v;
i2 = a - v;
return 2;
}
}
void _tangents(point c, ld r1, ld r2, vector<line> &ans) {
ld r = r2 - r1;
ld z = sq(c.x) + sq(c.y);
ld d = z - sq(r);
if (sign(d) == -1)
return;
d = sqrt(abs(d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back(l);
}
// tangents between two circles
vector<line> tangents(point o1, ld r1, point o2, ld r2) {
vector<line> ans;
for (int i = -1; i <= 1; i += 2)
for (int j = -1; j <= 1; j += 2)
_tangents(o2 - o1, r1 * i, r2 * j, ans);
for (int i = 0; i < (int)ans.size(); ++i)
ans[i].c -= ans[i].a * o1.x + ans[i].b * o1.y;
return ans;
}
#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 11 "verify/geometry/igor-tests/12.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
point o;
ld r;
line l;
cin >> o.x >> o.y >> r >> l.a >> l.b >> l.c;
point I1, I2;
l.norm();
int ans = intersect(o, r, l, I1, I2);
if (!ans) {
cout << ans << endl;
} else if (ans == 1) {
cout << ans << "\n" << I1.x << " " << I1.y << endl;
} else if (ans == 2) {
cout << ans << "\n" << I1.x << " " << I1.y << "\n" << I2.x << " " << I2.y << endl;
}
}
#line 41 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a12 {
#line 1 "verify/geometry/igor-tests/13.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 D - Площадь многоугольника
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/13.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/Tangents.cpp"
/**
* Author: Igor Markelov
* Date: 2022-11-18
* Description: Tangents to circles.
*/
// tangents from point to circle
int tangents(point &o, ld r, point &p, point &i1, point &i2) {
ld ln = len(o - p);
int sgn = sign(ln - r);
if (sgn == -1) {
return 0;
} else if (sgn == 0) {
i1 = p;
return 1;
} else {
ld x = sq(r) / ln;
vec v = norm(p - o) * x;
point a = o + v;
v = ort(norm(p - o)) * sqrt(sq(r) - sq(x));
i1 = a + v;
i2 = a - v;
return 2;
}
}
void _tangents(point c, ld r1, ld r2, vector<line> &ans) {
ld r = r2 - r1;
ld z = sq(c.x) + sq(c.y);
ld d = z - sq(r);
if (sign(d) == -1)
return;
d = sqrt(abs(d));
line l;
l.a = (c.x * r + c.y * d) / z;
l.b = (c.y * r - c.x * d) / z;
l.c = r1;
ans.push_back(l);
}
// tangents between two circles
vector<line> tangents(point o1, ld r1, point o2, ld r2) {
vector<line> ans;
for (int i = -1; i <= 1; i += 2)
for (int j = -1; j <= 1; j += 2)
_tangents(o2 - o1, r1 * i, r2 * j, ans);
for (int i = 0; i < (int)ans.size(); ++i)
ans[i].c -= ans[i].a * o1.x + ans[i].b * o1.y;
return ans;
}
#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 11 "verify/geometry/igor-tests/13.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
int n;
cin >> n;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
ld ans = 0;
for (int i = 0; i < n; ++i) {
ans += p[i] % p[(i + 1) % n];
}
ans = abs(ans) / 2;
cout << (ll)(ans) << (sign(ans - (ll)ans) == 1 ? ".5" : "") << endl;
}
#line 44 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a13 {
#line 1 "verify/geometry/igor-tests/14.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 E - Точка в многоугольнике
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/14.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 11 "verify/geometry/igor-tests/14.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
#ifndef LOCAL
freopen("point.in", "r", stdin);
freopen("point.out", "w", stdout);
#endif
int n;
cin >> n;
point a;
cin >> a.x >> a.y;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
if (isIn(p, a)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
#line 47 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a14 {
#line 1 "verify/geometry/igor-tests/15.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 F - Выпукл ли многоугольник
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/15.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/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 9 "verify/geometry/igor-tests/15.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
int n;
cin >> n;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
if (hull(p, true).size() == n) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
#line 50 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a15 {
#line 1 "verify/geometry/igor-tests/16.cpp"
// Yandex Algo 2023-2024. C. Геометрия 2 G - Теодор Рузвельт
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=55063
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/16.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 11 "verify/geometry/igor-tests/16.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
int n, m, k;
cin >> n >> m >> k;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
int cnt = 0;
for (int i = 0; i < m; ++i) {
point a;
cin >> a.x >> a.y;
if (isInConvex(p, a)) {
++cnt;
}
}
if (cnt >= k) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
#line 53 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a16 {
#line 1 "verify/geometry/igor-tests/17.cpp"
// Yandex Algo 2023-2024. B'. Геометрия 2 B - Замок
// https://ejudge.algocode.ru/cgi-bin/new-client?contest_id=54021
#define main main228
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/17.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 11 "verify/geometry/igor-tests/17.cpp"
signed main() {
cin.tie(0)->sync_with_stdio(0);
cout.precision(20), cout.setf(ios::fixed);
int n;
cin >> n;
vector<vector<point>> p(n);
vector<ld> areas(n);
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
p[i].resize(k);
for (auto& [x, y] : p[i]) {
cin >> x >> y;
}
ld area = 0;
for (int j = 0; j < k; ++j) {
area += p[i][j] % p[i][(j + 1) % k];
}
area /= 2;
area = abs(area);
areas[i] = area;
}
vector<int> order(n);
iota(all(order), 0);
sort(all(order), [&](int lhs, int rhs) -> bool { return areas[lhs] < areas[rhs]; }); vector<bool> used(n); int q; cin >> q; for (int i = 0; i < q; ++i) { point a; cin >> a.x >> a.y; int L = -1, R = n; while (L < R - 1) { int M = (L + R) / 2; if (isInConvex(p[order[M]], a)) { R = M; } else { L = M; } } if (R < n) used[R] = true; } ld ans = 0; for (int i = 0; i < n; ++i) { if (used[i]) { ans += areas[order[i]] - (i > 0 ? areas[order[i - 1]] : 0); } } // NOLINT
cout << ans << endl;
}
#line 56 "verify/geometry/igor-tests/include-all.test.cpp"
};
namespace a17 {
#line 1 "verify/geometry/igor-tests/20.cpp"
// 2021-2022 ICPC NERC (NEERC), North-Western Russia Regional Contest
// (Northern Subregionals) G https://codeforces.com/gym/104011/problem/G
#define main main2
#line 1 "contest/template.cpp"
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#line 5 "contest/template.cpp"
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 5 "verify/geometry/igor-tests/20.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 11 "verify/geometry/igor-tests/20.cpp"
int main() {
cout.precision(20), cout.setf(ios::fixed);
int n;
cin >> n;
vector<point> p(n);
for (auto& [x, y] : p) {
cin >> x >> y;
}
int pos = min_element(all(p)) - p.begin();
rotate(p.begin(), p.begin() + pos, p.end());
vector<point> v;
for (int i = 0; i < n; ++i) {
v.push_back(p[i + 1 < n ? i + 1 : 0] - p[i]);
}
vector<int> fpos(n);
for (int i = 0; i < n; ++i) {
int pos = lower_bound(all(v), point{0,0} - v[i], cmpHalf) - v.begin();
pos = pos % n;
fpos[i] = pos;
}
auto check = [&](ld x) -> bool {
vector<line> lines;
lines.reserve(2 * n);
auto addLine = [&](int i, int j) {
vec v1 = (p[j] - p[i]) * (x / (x + 1));
vec v2 = (p[j + 1 < n ? j + 1 : 0] - p[i]) * (x / (x + 1));
lines.push_back(getln(p[i] + v1, p[i] + v2));
};
for (int i = 0; i < n; ++i) {
int pos = fpos[i];
addLine(i, pos);
addLine(pos, i);
}
return !isHpiEmpty(lines);
};
ld L = 1, R = 2;
for (int it = 0; it < 19; ++it) {
ld M = sqrt(L * R);
if (check(M)) {
R = M;
} else {
L = M;
}
}
cout << sqrt(L * R) << endl;
}
#line 59 "verify/geometry/igor-tests/include-all.test.cpp"
};
void test() {
}
int main() {
int a, b;
cin >> a >> b;
if (a == 1234 && b == 5678) test();
cout << a + b << endl;
}