SHARE
TWEET

Untitled

Galebickosikasa Sep 21st, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC target("avx,avx2")
  2. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  3. #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,tune=native")
  4. #pragma GCC optimize("03")
  5.  
  6. #include <iostream>
  7. #include <vector>
  8. #include <cmath>
  9. #include <numeric>
  10. #include <algorithm>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13. #include <set>
  14. #include <map>
  15.  
  16. #define pb push_back
  17. #define ll long long
  18. #define ld long double
  19. #define all(a) a.begin(), a.end()
  20. #define sz(a) (int)a.size()
  21.  
  22. using namespace std;
  23.  
  24. //tg: @galebickosikasa
  25.  
  26. const ld eps = 1e-12;
  27. const ld pi = 3.14159265358979323846264;
  28. const ld inf = 1e18;
  29.  
  30. bool eq(ld a, ld b){
  31.     return fabs(a - b) < eps;
  32. }
  33.  
  34. struct Vector{
  35.     ld x, y;
  36.  
  37.     Vector(ld _x = 0, ld _y = 0){
  38.         x = _x, y = _y;
  39.     }
  40.  
  41.     Vector(Vector a, Vector b){
  42.         *this = b - a;
  43.     }
  44.  
  45.     ld len(){
  46.         return sqrt(*this * *this);
  47.     }
  48.  
  49.     void normalize(){
  50.         *this = *this / len();
  51.     }
  52.  
  53.     Vector rotate_ccw(){
  54.         return Vector(-y, x);
  55.     }
  56.  
  57.     Vector anti_rotate_ccw(){
  58.         return Vector(y, -x);
  59.     }
  60.  
  61.     Vector operator + (Vector other){
  62.         return Vector(x + other.x, y + other.y);
  63.     }
  64.  
  65.     Vector operator - (){
  66.         return Vector(-x, -y);
  67.     }
  68.  
  69.     Vector operator - (Vector other){
  70.         return *this + -other;
  71.     }
  72.  
  73.     Vector operator * (ld lambda){
  74.         return Vector(x * lambda, y * lambda);
  75.     }
  76.  
  77.     Vector operator / (ld lambda){
  78.         return Vector(x / lambda, y / lambda);
  79.     }
  80.  
  81.     ld operator ^ (Vector other){
  82.         return x * other.y - other.x * y;
  83.     }
  84.  
  85.     ld operator * (Vector other){
  86.         return x * other.x + y * other.y;
  87.     }
  88.  
  89.     bool operator == (const Vector other) const{
  90.         return eq(x, other.x) && eq(y, other.y);
  91.     }
  92.  
  93. };
  94.  
  95. struct Line{
  96.     ld a, b, c;
  97.  
  98.     Line (Vector p, Vector q){
  99.         Vector pq(p, q);
  100.         Vector n = pq.rotate_ccw();
  101.         a = -n.x, b = -n.y, c = p * n;
  102.     }
  103.  
  104.     Line (ld _a = 1, ld _b = 1, ld _c = 0){
  105.         a = _a, b = _b, c = _c;
  106.     }
  107.  
  108.     Vector n(){
  109.         return Vector(a, b);
  110.     }
  111.  
  112.     bool parallel(Line other){
  113.         return eq(a / b, other.a / other.b);
  114.     }
  115.  
  116.     pair<int, Vector> intersect(Line other){
  117.         if (parallel(other)){
  118.             return {0, Vector()};
  119.         } if (*this == other){
  120.             return {2, Vector()};
  121.         }
  122.         Vector t;
  123.         t.x = (other.c * b - c * other.b) / (n() ^ other.n());
  124.         t.y =  -(other.c * a - c * other.a) / (n() ^ other.n());
  125.         return {1, t};
  126.     }
  127.  
  128.     bool operator == (Line& other) const{
  129.         return eq(a / a, other.a / other.a) && eq(b / a, other.b / other.a) && eq(c / a, other.c / other.a);
  130.     }
  131.  
  132.     Vector random_point(){
  133.         Vector t;
  134.         t.x = -(a * c) / (a * a + b * b), t.y = -(b * c) / (a * a + b * b);
  135.         return t;
  136.     }
  137.  
  138.     bool belongs(Vector v){
  139.         return eq(a * v.x + b * v.y + c, 0);
  140.     }
  141.  
  142.     Vector projection(Vector p){
  143.         Vector z = n();
  144.         Line tmp(p, p + z);
  145.         pair<int, Vector> q = intersect(tmp);
  146.         return q.second;
  147.     }
  148.  
  149. }; // s = v + g / 2 - 1
  150.  
  151. ll gcd(ll a, ll b){
  152.     if (b == 0){
  153.         return a;
  154.     }
  155.     return gcd(b, a % b);
  156. }
  157.  
  158. bool is_on(Vector a, Vector b, Vector k){
  159.     return eq(Vector(a, k) ^ Vector(a, b), 0) && Vector(a, k) * Vector(a, b) >= 0 && Vector(b, k) * Vector(b, a) >= 0;
  160. }
  161.  
  162. struct Polygon{
  163.     vector<Vector> vertices;
  164.  
  165.     ll doubled_area(){
  166.         ll ans = 0;
  167.         vertices.pb(vertices.front());
  168.         for (int i = 0; i < vertices.size() - 1; ++i){
  169.             ans += (ll)(vertices[i] ^ vertices[i + 1]);
  170.         }
  171.         vertices.pop_back();
  172.         return fabs(ans);
  173.     }
  174.     ld area(){
  175.         return doubled_area() / 2.0;
  176.     }
  177.  
  178.     ll count_of_point(){
  179.         auto s = doubled_area();
  180.         ll cnt = 0;
  181.         vertices.pb(vertices.front());
  182.         for (int i = 0; i < vertices.size() - 1; ++i){
  183.             int x = gcd(abs((ll)vertices[i].x - (ll)vertices[i + 1].x), abs((ll)vertices[i].y - (ll)vertices[i + 1].y));
  184.             cerr << x << '\n';
  185.             cnt += x;
  186.         }
  187.         vertices.pop_back();
  188.         ll v = (s - cnt + 2) / 2;
  189.         return v;
  190.     }
  191.  
  192. };
  193.  
  194. struct Circle{
  195.     Vector o;
  196.     ld r;
  197.  
  198.     Circle (Vector A, Vector B, Vector C){
  199.         Vector a(B, C);
  200.         Vector b(A, C);
  201.         a = a / 2, b = b / 2;
  202.         Vector m = B + a, n = A + b;
  203.         Line tmp1(m, m + a.rotate_ccw());
  204.         Line tmp2(n, n + b.rotate_ccw());
  205.         auto t = tmp1.intersect(tmp2);
  206.         o = t.second;
  207.         r = Vector(o, A).len();
  208.     }
  209.  
  210.     Circle (Vector _o = Vector(), ld _r = 1){
  211.         o = _o;
  212.         r = _r;
  213.     }
  214.  
  215.     pair<int, pair<Vector, Vector>> intersect(Line l){
  216.         Vector h = l.projection(o);
  217.         Vector oh(o, h);
  218.         if (oh.len() > r){
  219.             return {0, {Vector(), Vector()}};
  220.         } else if (eq(oh.len(), r)){
  221.             return {1, {h, Vector()}};
  222.         } else{
  223.             double ah = sqrt(r * r - oh * oh);
  224.             Vector a = l.n();
  225.             a = a.rotate_ccw();
  226.             a.normalize();
  227.             a = a * ah;
  228.             Vector tmp1 = h + a;
  229.             Vector tmp2 = h - a;
  230.             return {2, {tmp1, tmp2}};
  231.         }
  232.     }
  233.  
  234.     pair<int, pair<Vector, Vector>> intersect(Circle other){
  235.         if (o == other.o && !eq(r, other.r)){
  236.             return {0, {Vector(), Vector()}};
  237.         }
  238.         Line l(2 * other.o.x - 2 * o.x, 2 * other.o.y - 2 * o.y, o.x * o.x - other.o.x * other.o.x + o.y * o.y - other.o.y * other.o.y - r * r + other.r * other.r);
  239.         return intersect(l);
  240.     }
  241.  
  242.     pair<int, pair<Vector, Vector>> tangent(Vector p){
  243.         if (Vector(p, o).len() < r){
  244.             return {0, {Vector(), Vector()}};
  245.         }
  246.         Vector t(o, p);
  247.         ld dist = sqrt(t * t - r * r);
  248.         Circle tmp(p, dist);
  249.         return intersect(tmp);
  250.     }
  251.  
  252.     bool operator == (const Circle& other) const{
  253.         return o == other.o && eq(r, other.r);
  254.     }
  255.  
  256.     ld leght_of_part(ld corner){
  257.         return r * corner;
  258.     }
  259.  
  260.     bool is_on(Vector v){
  261.         return eq(Vector(o, v).len(), r);
  262.     }
  263.  
  264. };
  265.  
  266. istream& operator >> (istream& in, Vector& v){
  267.     in >> v.x >> v.y;
  268.     return in;
  269. }
  270.  
  271. ostream& operator << (ostream& out, const Vector& v){
  272.     out << v.x << ' ' << v.y;
  273.     return out;
  274. }
  275.  
  276. istream& operator >> (istream& in, Circle& v){
  277.     in >> v.o >> v.r;
  278.     return in;
  279. }
  280.  
  281. istream& operator >> (istream& in, Line& v){
  282.     in >> v.a >> v.b >> v.c;
  283.     return in;
  284. }
  285.  
  286. istream& operator >> (istream& in, Polygon& s){
  287.     int n;
  288.     in >> n;
  289.     s.vertices = vector<Vector> (n);
  290.     for (int i = 0; i < n; ++i){
  291.         in >> s.vertices[i];
  292.     }
  293.     return in;
  294. }
  295.  
  296. ld dist_to_segment(Vector a, Vector b, Vector x){
  297.     Line t(a, b);
  298.     auto p = t.projection(x);
  299.     if (is_on(a, b, p)){
  300.         return Vector(x, p).len();
  301.     }
  302.     return min(Vector(x, b).len(), Vector(x, a).len());
  303. }
  304.  
  305. ld dist_to_sun(Vector a, Vector b, Vector x){
  306.     Line t(a, b);
  307.     auto p = t.projection(x);
  308.     Vector tmp1(a, p);
  309.     Vector tmp2(a, b);
  310.     if (tmp1 * tmp2 >= 0){
  311.         return Vector(x, p).len();
  312.     }
  313.     return Vector(a, x).len();
  314. }
  315.  
  316. ld dist_to_line(Vector a, Vector b, Vector x){
  317.     Line t(a, b);
  318.     auto p = t.projection(x);
  319.     return Vector(x, p).len();
  320. }
  321.  
  322. bool intersection(Vector a, Vector b, Vector c, Vector d){
  323.     Line x(a, b);
  324.     Line y(c, d);
  325.     if (a == b && c == d && !(a == c)){
  326.         return false;
  327.     }
  328.     if (a == b){
  329.         return is_on(c, d, a);
  330.     }
  331.     if (c == d){
  332.         return is_on(a, b, c);
  333.     }
  334.     if (is_on(d, a, c) || is_on(d, b, c) || is_on(b, c, a) || is_on(b, d, a)){
  335.         return true;
  336.     }
  337.     pair<int, Vector> q = x.intersect(y);
  338.     if (q.first == 0 || q.first == 2){
  339.         return false;
  340.     }
  341.     Vector z = q.second;
  342.     return is_on(a, b, z) && is_on(c, d, z);
  343. }
  344.  
  345. ld min(const vector<ld>& v){
  346.     ld m = inf;
  347.     for (auto& x: v){
  348.         m = min(m, x);
  349.     }
  350.     return m;
  351. }
  352.  
  353. ld dist_between_segments(Vector a, Vector b, Vector c, Vector d){
  354.     if (intersection(a, b, c, d)){
  355.         return 0;
  356.     }
  357.     Line tmp1(a, b);
  358.     Line tmp2(c, d);
  359.     vector<ld> dist;
  360.     auto tmpp1 = tmp1.projection(c), tmpp2 = tmp1.projection(d), tmpp3 = tmp2.projection(a), tmpp4 = tmp2.projection(b);
  361.     if (is_on(a, b, tmpp1)){
  362.         dist.pb(tmpp1.len());
  363.     } if (is_on(a, b, tmpp2)){
  364.         dist.pb(tmpp2.len());
  365.     } if (is_on(c, d, tmpp3)){
  366.         dist.pb(tmpp3.len());
  367.     } if (is_on(c, d, tmpp4)){
  368.         dist.pb(tmpp4.len());
  369.     }
  370.     dist.pb(Vector(a, c).len());
  371.     dist.pb(Vector(a, d).len());
  372.     dist.pb(Vector(b, d).len());
  373.     dist.pb(Vector(b, c).len());
  374.     return min(dist);
  375. }
  376.  
  377. int main(){
  378.     ios_base::sync_with_stdio(false);
  379.     cout.tie(nullptr);
  380.     cin.tie(nullptr);
  381.     cout.precision(15);
  382.     cout << fixed;
  383.  
  384.  
  385. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top