D.cpp

// Problem D: A Round Peg in a Ground Hole
// Author: Christopher Vo

#include <iostream>
#include <cmath>
using namespace std;

struct Point
{
  double x, y;
};

// returns value of ab x ac
double cross(const Point & a, const Point & b, const Point & c)
{
  return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

// return distance between a and b
double dist(const Point & a, const Point & b)
{
  return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

// is v convex?
bool isConvex(Point v[], int n)
{
  double dir = 0;
  for (int i = 0; i < n; ++i) {
    double left = cross(v[i], v[(i + 1) % n], v[(i + 2) % n]);
    if (dir == 0)
      dir = left;
    if (dir < 0 && left > 0 || dir > 0 && left < 0)
      return false;
  }
  return true;
}

// does the peg fit in the hole?
bool pegFits(Point v[], int n, const Point & peg, double pegRad)
{
  double dir = 0;
  for (int i = 0; i < n; ++i) {
    int i2 = (i + 1) % n;
    // check line segment intersection with peg
    // d = distance from line segment to peg center
    double d = abs(cross(v[i], v[i2], peg) / dist(v[i], v[i2]));
    if (d < pegRad)
      return false;
    // check if peg changes sides of polygon line
    double left = cross(v[i], v[i2], peg);
    if (dir == 0)
      dir = left;
    if (dir < 0 && left > 0 || dir > 0 && left < 0)
      return false;
  }
  return true;
}

int main()
{
  int n;
  while (cin >> n) {
    if (n < 3)
      break;
    double pegRad;
    Point peg;
    cin >> pegRad >> peg.x >> peg.y;
    double vertexX, vertexY;
    Point v[n];
    for (int i = 0; i < n; i++)
      cin >> v[i].x >> v[i].y;
    if (!isConvex(v, n))
      cout << "HOLE IS ILL-FORMED" << endl;
    else if (!pegFits(v, n, peg, pegRad))
      cout << "PEG WILL NOT FIT" << endl;
    else
      cout << "PEG WILL FIT" << endl;
  }
  return 0;
}

D.java

// Problem D: A Round Peg in a Ground Hole
// Author: Christopher Vo

import java.awt.geom.*;
import java.util.*;

public class D {

  static int leftOf(Point2D a, Point2D b, Point2D c) {
    // returns 1 if c is left of line ab
    // returns 0 if c is co-linear to line ab
    // returns -1 if c is right of line ab
    double z = (b.getX() - a.getX()) * (c.getY() - a.getY())
        - (c.getX() - a.getX()) * (b.getY() - a.getY());
    return (int) Math.signum(z);
  }

  static boolean isConvex(ArrayList<Point2D> v) {
    // is the polygon v convex?
    int dir = 0, nv = v.size();
    for (int i = 0; i < nv; ++i) {
      Point2D p1 = v.get(i);
      Point2D p2 = v.get((i + 1) % nv);
      Point2D p3 = v.get((i + 2) % nv);
      int left = leftOf(p1, p2, p3);
      if (dir == 0)
        dir = left;
      if (dir < 0 && left > 0 || dir > 0 && left < 0)
        return false;
    }
    return true;
  }

  static boolean pegFits(ArrayList<Point2D> v, Point2D peg, double pegRad) {
    // does the peg fit in the polygon?
    int dir = 0, nv = v.size();
    for (int i = 0; i < nv; ++i) {
      Point2D p1 = v.get(i);
      Point2D p2 = v.get((i + 1) % nv);
      // check if any line segments intersect with the peg
      if(new Line2D.Double(p1, p2).ptSegDist(peg) < pegRad)
        return false;
      // check if peg suddenly changes sides
      int left = leftOf(p1, p2, peg);
      if (dir == 0)
        dir = left;
      if(dir < 0 && left > 0 || dir > 0 && left < 0)
        return false;
    }
    return true;
  }

  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    while (s.hasNextInt()) {
      int nVertices = s.nextInt();
      if (nVertices < 3)
        break;
      double pegRadius = s.nextDouble();
      Point2D peg = new Point2D.Double(s.nextDouble(), s.nextDouble());
      ArrayList<Point2D> v = new ArrayList<Point2D>();
      for (int i = 0; i < nVertices; i++)
        v.add(new Point2D.Double(s.nextDouble(), s.nextDouble()));
      if (!isConvex(v))
        System.out.println("HOLE IS ILL-FORMED");
      else if (!pegFits(v, peg, pegRadius))
        System.out.println("PEG WILL NOT FIT");
      else
        System.out.println("PEG WILL FIT");
    }
  }
}