Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <random>
- #include <set>
- #include <iomanip>
- using namespace std;
- const int N = 5e5 + 7;
- const long long INF = -1;
- const long double eps = 1e-9;
- struct vect {
- long double x, y;
- };
- vect operator+(vect a, vect b)
- {
- return { a.x + b.x, a.y + b.y };
- }
- vect operator-(vect& a, vect& b)
- {
- return { a.x - b.x, a.y - b.y };
- }
- vect operator*(vect& a, long double x)
- {
- return { a.x * x, a.y * x };
- }
- vect operator/(vect& a, long double x)
- {
- return { a.x / x, a.y / x };
- }
- long double operator %(const vect& a, const vect& b) { // vect
- return a.x * b.y - a.y * b.x;
- }
- long double operator *(const vect& a, const vect& b) { // skal
- return a.x * b.x + a.y * b.y;
- }
- bool operator==(vect& a, vect& b)
- {
- return abs(a.x - b.x) < eps && abs(b.y - a.y) < eps;
- }
- long double len(vect a)
- {
- return sqrtl(a.x * a.x + a.y * a.y);
- }
- vect norm(vect a, long double x)
- {
- long double l = len(a);
- a = a / l;
- a = a * x;
- return a;
- }
- vect perp(vect a)
- {
- return { a.y * -1, a.x };
- }
- vector<vect> PerOkr(vect o1, long double r1, vect o2, long double r2)
- {
- vector<vect> ans;
- ans.clear();
- vect o2o1 = o1 - o2;
- long double z = len(o2o1);
- if (abs(r1 - r2) < eps && o1 == o2) {
- ans.push_back({ 1, 1 });
- ans.push_back({ 2, 2 });
- ans.push_back({ 3, 3 });
- return ans;
- }
- if (abs(z - r1 - r2) < eps) {
- ans.push_back(o2 + norm(o2o1, r2));
- return ans;
- }
- if (z > r1 + r2 + eps) { //
- return ans;
- }
- if (abs(z + r1 - r2) < eps) { // z == r1+r2, vnutr kas
- ans.push_back(o2 + norm(o2o1, r2));
- return ans;
- }
- if (abs(z + r2 - r1) < eps) { // z + r2 == r1, vnutr kas
- ans.push_back(o1 + norm(o2o1 * -1, r1));
- return ans;
- }
- if (z + r2 < r1 + eps || z + r1 < r2 + eps) { // odin vnutri drugogo
- return ans;
- }
- long double x = (z - (r1 * r1 - r2 * r2) / z) / 2;
- long double y = sqrtl(r2 * r2 - x * x);
- vect h = o2 + norm(o2o1, x);
- vect per = norm(perp(o2o1), y);
- cout << fixed << setprecision(10);
- vect o1h = h - o1;
- ans.push_back(h + per);
- ans.push_back(h - per);
- return ans;
- }
- vector<vect> Kas(vect o1, long double r1, vect o2) {
- vector<vect> ans;
- vect o2o1 = o1 - o2;
- long double z = len(o2o1);
- if (z < r1 - eps) {
- return ans;
- }
- if (abs(z - r1) < eps) {
- ans.push_back(o2);
- return ans;
- }
- long double r2 = sqrtl(z * z - r1 * r1);
- return PerOkr(o1, r1, o2, r2);
- }
- vect Intersect(vect a, vect b, vect c, vect d) {
- long double a1 = b.y - a.y;
- long double b1 = a.x - b.x;
- long double c1 = -1 * (a1 * a.x + b1 * a.y);
- long double a2 = d.y - c.y;
- long double b2 = c.x - d.x;
- long double c2 = -1 * (a1 * c.x + b1 * c.y);
- long double D = a1 * b2 - a2 * b1;
- long double Dx = c1 * b2 - c2 * b1;
- long double Dy = a1 * c2 - a2 * c1;
- if (D == 0) {
- return { -1337, -1448 };
- }
- return { -1 * (Dx / D), -1 * (Dy / D) };
- }
- long double RasstDoOtr(vect a, vect b, vect c) {
- vect ca = a - c;
- vect cb = b - c;
- vect bc = c - b;
- vect ba = a - b;
- vect ac = c - a;
- vect ab = b - a;
- if (ab * ac <= 0 || ba * bc <= 0) {
- return min(len(ac), len(bc));
- }
- return abs((ca % cb) / len(ab));
- }
- bool intC(vect o, long double r, vect a, vect b) {
- return RasstDoOtr(a, b, o) <= r + eps;
- }
- vect o, v, k;
- long double r1, r2, n, ans;
- vector<vect> ans1, ans2;
- int main()
- {
- cin >> v.x >> v.y >> k.x >> k.y >> o.x >> o.y >> r1;
- cout << fixed << setprecision(10);
- if (!intC(o, r1, v, k)) {
- cout << len(k - v);
- return 0;
- }
- ans1 = Kas(o, r1, v);
- ans2 = Kas(o, r1, k);
- ans = 1e12;
- for (int i = 0; i < ans1.size(); i++) {
- for (int j = 0; j < ans2.size(); j++) {
- vect oi = ans1[i] - o;
- vect oj = ans2[j] - o;
- //long double sect = min(abs(atan2(oi % oj, oi * oj)) * r1, 2 * acos(-1) * r1 - abs(atan2(oi % oj, oi * oj)) * r1);
- long double sect = abs(atan2(oi % oj, oi * oj)) * r1;
- ans = min(ans, len(v - ans1[i]) + len(k - ans2[j]) + sect);
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement