Летняя школа по компьютерным наукам 2018

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const ld pi = acos(-1), eps = 1e-6, INF = 1e16;

bool isEqual(ld x, ld y)
{
    return fabs(x - y) < eps;
}

int sgn(ld sc)
{
    if (isEqual(sc, 0)) return 0;
    if (sc < eps) return -1;
    return 1;
}

struct pnt
{
    ld x, y;
    pnt(){}
    pnt(ld _x, ld _y)
    {
        x = _x, y = _y;
    }
    pnt operator +(pnt p)
    {
        return pnt(x + p.x, y + p.y);
    }
    pnt operator -(pnt p)
    {
        return pnt(x - p.x, y - p.y);
    }
    void operator += (pnt p)
    {
        x += p.x, y += p.y;
    }
    void operator -= (pnt p)
    {
        x -= p.x, y -= p.y;
    }
    pnt operator * (ld sc)
    {
        return pnt(x * sc, y * sc);
    }
    pnt operator / (ld sc)
    {
        return pnt(x / sc, y / sc);
    }
    ld operator * (pnt p)
    {
        return x * p.x + y *p.y;
    }
    ld operator ^ (pnt p)
    {
        return x * p.y - p.x * y;
    }
    bool operator == (pnt p)
    {
        return isEqual(x, p.x) && isEqual(y, p.y);
    }
    bool operator != (pnt p)
    {
        return !isEqual(x, p.x) || !isEqual(y, p.y);
    }
    void normalize()
    {
        ld sq = sqrt(x *x + y * y);
        x /= sq;
        y /= sq;
        return;
    }
    ld dist2(pnt p)
    {
        return (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);
    }
    ld dist(pnt p)
    {
        return sqrt(dist2(p));
    }
    bool isParallel(pnt p)
    {
        return isEqual(pnt(x, y) ^ p, 0);
    }
};

struct line
{
    ld a, b, c;
    line(){}
    line(ld _a, ld _b, ld _c)
    {
        a = _a, b = _b, c = _c;
    }
    line(pnt p1, pnt p2)
    {
        a = p1.y - p2.y;
        b = p2.x - p1.x;
        c = -(a * p1.x + b * p1.y);
    }
    pnt getPerpendicularVector()
    {
        return pnt(a, b);
    }
    pnt getParallelVector()
    {
        return pnt(-b, a);
    }
    line getPerpendicularLine()
    {
        return line(-b, a, c);
    }
    bool isParallel(line l)
    {
        return getParallelVector().isParallel(l.getParallelVector());
    }
    pnt intersect(line l)
    {
        if (isParallel(l)){
            return pnt(INF, INF);
        }
        ld q = a * l.b - b * l.a;
        return pnt((b * l.c - c * l.b) / q, (c * l.a - a * l.c) / q);
    }
    ld dist(pnt p)
    {
        return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
    }
    pnt basePerp(pnt p)
    {
        return intersect(line(p, p + getPerpendicularVector()));
    }
    bool isOnLine(pnt p)
    {
        return isEqual(a * p.x + b * p.y + c, 0);
    }

};

struct circle{
    pnt center;
    ld r;
    circle(){}
    circle(pnt _center, ld _r)
    {
        center = _center, r = _r;
    }
    // p1 и p2 - концы диаметра
    circle(pnt p1, pnt p2)
    {
        center = (p1 + p2) / 2;
        r = p1.dist(center);
    }
    circle(pnt p1, pnt p2, pnt p3)
    {
        pnt m1 = (p1 + p3) / 2, m2 = (p2 + p3) / 2;
        line l1 = line(p1, p3), l2 = line(p2, p3);
        line s1 = line(m1, m1 + l1.getPerpendicularVector());
        line s2 = line(m2, m2 + l2.getPerpendicularVector());
        center = s1.intersect(s2);
        r = center.dist(p1);
    }
    ld s()
    {
        return pi * r * r;
    }
    ld l()
    {
        return 2 * pi * r;
    }
    vector <pnt> intersect(line l)
    {
        vector <pnt> ans;
        ld d = l.dist(center);
        if (!isEqual(d, r) && d > r) return ans;
        if (isEqual(d, r))
        {
            ans.push_back(l.basePerp(center));
            return ans;
        }
        pnt p = l.basePerp(center);
        pnt vec = l.getParallelVector();
        vec.normalize();
        vec = vec * sqrt(r * r - d * d);
        ans.push_back(p + vec);
        ans.push_back(p - vec);
        return ans;
    }
    vector <pnt> intersect(circle c)
    {
        ld x1 = center.x, y1 = center.y, x2 = c.center.x, y2 = c.center.y, r1 = r, r2 = c.r;
        line l = line(2 * (x2 - x1), 2 * (y2 - y1), x1 * x1 + y1 * y1 - x2 * x2 - y2 * y2 + r2 * r2 - r1 * r1);
        return intersect(l);
    }
    bool isInside(pnt p)
    {
        return center.dist(p) < r && !isEqual(center.dist(p), r);
    }
    vector <pnt> tangent(pnt p)
    {
        circle c = circle(p, center);
        return intersect(c);
    }
};


int main()
{

    return 0;
}