未整理

説明

どこに置こう？

ソースコード

// PKU 2235 (Triangularize the Convex Hull)
bool intriangle(point a, point b, point c, point p) {
  a -= p; b -= p; c -= p;
  return cross(a, b) >= 0 &&
         cross(b, c) >= 0 &&
         cross(c, a) >= 0;
}
bool incircle(point a, point b, point c, point p) {
  a -= p; b -= p; c -= p;
  return norm(a) * cross(b, c)
       + norm(b) * cross(c, a)
       + norm(c) * cross(a, b) >= 0; // < : inside, = cocircular, > outside
}

// UVA 438 (The Circumference of the Circle)
point three_point_circle(const point& a, const point& b, const point& c) {
  point x = 1.0/conj(b - a), y = 1.0/conj(c - a);
  return (y-x)/(conj(x)*y - x*conj(y)) + a;
}

// UVA 453 (Intersecting Circles)
pair<point, point> circle_circle_intersect(
    const point& c1, const double& r1, const point& c2, const double& r2) {
  point A = conj(c2-c1), B = (r2*r2-r1*r1-(c2-c1)*conj(c2-c1)), C = r1*r1*(c2-c1);
  point D = B*B-4.0*A*C;
  point z1 = (-B+sqrt(D))/(2.0*A)+c1, z2 = (-B-sqrt(D))/(2.0*A)+c1;
  return pair<point, point>(z1, z2);
}