Advertisement
Guest User

Untitled

a guest
Sep 19th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define db long double
  4. #define x first
  5. #define y second
  6. #define mp make_pair
  7. #define pb push_back
  8. #define all(a) a.begin(), a.end()
  9.  
  10. using namespace std;
  11.  
  12. struct pt{
  13.     ll x, y;
  14.     pt() {}
  15.     pt(ll x, ll y): x(x), y(y) {}
  16.     pt operator-(const pt& nxt) const { return pt(x - nxt.x, y - nxt.y); }
  17.     pt operator+(const pt& nxt) const { return pt(x + nxt.x, y + nxt.y); }
  18.     bool operator==(const pt& nxt) const { return x == nxt.x && y == nxt.y; }
  19.     ll operator*(const pt& nxt) const { return x * nxt.x + y * nxt.y; }
  20.     ll operator%(const pt& nxt) const { return x * nxt.y - y * nxt.x; }
  21.     db len() const { return sqrtl(x * x + y * y); }
  22.     ll sq_len() const { return x * x + y * y; }
  23. };
  24.  
  25. ll convert(string s){
  26.     int sign = 1;
  27.     if (s.size() && s[0] == '-') sign = -1, reverse(all(s)), s.pop_back(), reverse(all(s));
  28.     ll ans = 0, ans2 = 0;
  29.     bool f = 0;
  30.     for (auto c : s){
  31.         if (c >= '0' && c <= '9'){
  32.             if (!f) ans = ans * 10 + (c - '0');
  33.             else ans2 = ans2 * 10 + (c - '0');
  34.         } else {
  35.             f = 1;
  36.         }
  37.     }
  38.  
  39.     if (ans2 < 10) ans2 *= 10;
  40.     return (ans * 100 + ans2) * sign;
  41. }
  42.  
  43. struct line{
  44.     ll a, b, c;
  45.     line() {}
  46.     line(pt w1, pt w2){
  47.         a = w2.y - w1.y;
  48.         b = w1.x - w2.x;
  49.         c = -(a * w1.x + b * w1.y);
  50.     }
  51. };
  52.  
  53. int sign(ll val){
  54.     if (val > 0) return 1;
  55.     if (val < 0) return -1;
  56.     return 0;
  57. }
  58.  
  59. const int CC = 6;
  60.  
  61. void solve(pt t, ll r, pt a, pt b){
  62.     if (a == b){
  63.         if ((a - t).sq_len() == r * r){
  64.             cout << 1 << "\n";
  65.             cout.precision(CC);
  66.             cout << fixed << (db)a.x / 100 << ' ' << (db)a.y / 100 << "\n";
  67.         } else {
  68.             cout << "0\n";
  69.         }
  70.         return;
  71.     }
  72.  
  73.     line l(a, b);
  74.    
  75.     if (r == 0){
  76.         if (l.a * t.x + l.b * t.y + l.c == 0){
  77.             cout.precision(CC);
  78.             if (((a - t) * (b - t)) <= 0) cout << "1\n", cout << fixed << (db)t.x / 100 << ' ' << (db)t.y / 100 << "\n";
  79.             else cout << "0\n";
  80.         } else {
  81.             cout << "0\n";
  82.         }
  83.         return;
  84.     }
  85.  
  86.     if (l.a * t.x + l.b * t.y + l.c == 0){
  87.         vector<pair<db, db> > ans;
  88.         pt v1 = a - t, v2 = b - t;
  89.         if (((a - t) * (b - t)) < 0){
  90.             if (v1.sq_len() >= r * r) ans.pb({ t.x + (db)v1.x / v1.len() * r, t.y + (db)v1.y / v1.len() * r });
  91.             if (v2.sq_len() >= r * r) ans.pb({ t.x + (db)v2.x / v2.len() * r, t.y + (db)v2.y / v2.len() * r });
  92.         } else {
  93.             if (v1.sq_len() < v2.sq_len()) swap(v1, v2);
  94.             if (v2.sq_len() <= r * r && r * r <= v1.sq_len()) ans.pb({ t.x + (db)v1.x / v1.len() * r, t.y + (db)v1.y / v1.len() * r });
  95.         }
  96.  
  97.         sort(all(ans));
  98.         cout << ans.size() << "\n";
  99.         cout.precision(CC);
  100.         for (auto c : ans) cout << fixed << c.x / 100 << ' ' << c.y / 100 << "\n";
  101.         return;
  102.     }
  103.  
  104.     ll d = abs(l.a * t.x + l.b * t.y + l.c);
  105.     ll f = l.a * l.a + l.b * l.b;
  106.     // d * d <= r * r * f
  107.     __int128_t val1 = d * (__int128_t)d;
  108.     __int128_t val2 = r * (__int128_t)r * (__int128_t)f;
  109.    
  110.     if (val1 > val2){
  111.         cout << "0\n";
  112.         return;
  113.     }
  114.  
  115.     pt v(l.a, l.b);
  116.     if ((a - t) % (b - t) > 0) swap(a, b);
  117.     if (sign((b - a) % (t - a)) == sign((b - a) % v)) v = { -v.x, -v.y };
  118.  
  119.     if (val1 == val2){
  120.         if ((v % (a - t)) >= 0 && ((b - t) % v) >= 0){
  121.             cout << "1\n";
  122.             cout.precision(CC);
  123.             cout << fixed << (t.x + (db)v.x / v.len() * r) / 100 << ' ' << (t.y + (db)v.y / v.len() * r) / 100 << "\n";;
  124.         } else {
  125.             cout << "0\n";
  126.         }
  127.     } else {
  128.         vector<pair<db, db> > ans;
  129.  
  130.         db dist = (db)d / sqrtl(f);
  131.         pair<db, db> sr = { t.x + (db)v.x / v.len() * dist, t.y + (db)v.y / v.len() * dist };
  132.         pair<db, db> v1 = { a.x - sr.x, a.y - sr.y };
  133.         pair<db, db> v2 = { b.x - sr.x, b.y - sr.y };
  134.         db m1 = sqrtl(v1.x * v1.x + v1.y * v1.y);
  135.         db m2 = sqrtl(v2.x * v2.x + v2.y * v2.y);
  136.         db le = sqrtl(r * r - dist * dist);
  137.  
  138.         if ((v % (a - t)) >= 0 && ((b - t) % v) >= 0){
  139.             if ((t - a).sq_len() >= r * r) ans.pb({ sr.x + v1.x / m1 * le, sr.y + v1.y / m1 * le });
  140.             if ((t - b).sq_len() >= r * r) ans.pb({ sr.x + v2.x / m2 * le, sr.y + v2.y / m2 * le });
  141.         } else {
  142.             pt w1 = a - t, w2 = b - t;
  143.             bool f = 0;
  144.             if (w1.sq_len() < w2.sq_len()) swap(w1, w2), f = 1;
  145.            
  146.             pair<db, db> v; db m;
  147.             if (!f){
  148.                 v = v1;
  149.                 m = m1;
  150.             } else {
  151.                 v = v2;
  152.                 m = m2;
  153.             }
  154.            
  155.             if (w2.sq_len() <= r * r && r * r <= w1.sq_len()) ans.pb({ sr.x + v.x / m * le, sr.y + v.y / m * le });
  156.         }
  157.  
  158.         sort(all(ans));
  159.         cout << ans.size() << "\n";
  160.         cout.precision(CC);
  161.         for (auto c : ans) cout << fixed << c.x / 100 << ' ' << c.y / 100 << "\n";
  162.     }
  163. }
  164.  
  165. int main(){
  166. #ifdef LOCAL
  167.     freopen("F_input.txt", "r", stdin);
  168.     //freopen("C_output.txt", "w", stdout);
  169. #endif
  170.     ios_base::sync_with_stdio(0);
  171.     cin.tie(0);
  172.     string x0, y0, r, x1, y1, x2, y2;
  173.     while(cin >> x0 >> y0 >> r >> x1 >> y1 >> x2 >> y2){
  174.         solve(pt(convert(x0), convert(y0)), convert(r), pt(convert(x1), convert(y1)), pt(convert(x2), convert(y2)));
  175.         cout << "\n";
  176.     }
  177. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement