cake/CakeCutting_artur.java

  1 import java.awt.geom.Point2D;
  2 import java.util.Comparator;
  3 import java.util.Scanner;
  4 import java.util.Set;
  5 import java.util.TreeSet;
  6 
  7 public class CakeCutting_artur {
  8 
  9   static final double eps = 1e-10;
 10 
 11   static final Comparator<Point2D.Double> comparator = new Comparator<Point2D.Double>() {
 12     public int compare(Point2D.Double p, Point2D.Double q) {
 13       if (p.distanceSq(q) < eps)
 14         return 0;
 15       return Math.abs(p.x - q.x) < eps ? Double.compare(p.y, q.y) : Double.compare(p.x, q.x);
 16     }
 17   };
 18 
 19   public static void main(String[] args) {
 20     Scanner in = new Scanner(System.in);
 21 
 22     // ax + by + c = 0
 23     long[][] line = new long[1001][3];
 24     // Intersection points in the circle
 25     Set<Point2D.Double> vertices = new TreeSet<Point2D.Double>(comparator);
 26     // Intersection points on the lines
 27     Set<Point2D.Double>[] segment = new Set[1001];
 28     for (int i = 0; i < segment.length; i++)
 29       segment[i] = new TreeSet<Point2D.Double>(comparator);
 30 
 31     while (true) {
 32       long cr = in.nextInt(), cx = in.nextInt(), cy = in.nextInt();
 33       int lines = in.nextInt();
 34       if (lines == 0 && cr == 0 && cx == 0 && cy == 0)
 35         break;
 36 
 37       int n = 0;
 38       for (int i = 0; i < lines; i++) {
 39         int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
 40         line[n][0] = y1 - y2;
 41         line[n][1] = x2 - x1;
 42         line[n][2] = y1 * (x1 - x2) - x1 * (y1 - y2);
 43 
 44         // delete line if does not cut
 45         long dist = line[n][0] * cx + line[n][1] * cy + line[n][2];
 46         long dot = line[n][0] * line[n][0] + line[n][1] * line[n][1];
 47         if (dist * dist >= dot * cr * cr)
 48           n--;
 49 
 50         // delete duplicate lines
 51         for (int j = 0; j < n; j++)
 52           if (same(line[n], line[j]))
 53             n--;
 54         n++;
 55       }
 56 
 57       vertices.clear();
 58       for (int i = 0; i < n; i++)
 59         segment[i].clear();
 60 
 61       for (int i = 0; i < n; i++)
 62         for (int j = 0; j < i; j++)
 63           if (!parallel(line[i], line[j])) {
 64             Point2D.Double p = intersect(line[i], line[j]);
 65             if (insideCircle(p, cx, cy, cr)) {
 66               vertices.add(p);
 67               segment[i].add(p);
 68               segment[j].add(p);
 69             }
 70           }
 71 
 72       int edges = 0;
 73       for (int i = 0; i < n; i++)
 74         edges += segment[i].size() + 1;
 75 
 76       // Euler's formula: vertices - edges + faces = 1
 77       System.out.println(1 + edges - vertices.size());
 78     }
 79   }
 80 
 81   static boolean insideCircle(Point2D.Double p, long cx, long cy, long cr) {
 82     return p.distanceSq(cx, cy) < cr * cr + eps;
 83   }
 84 
 85   static boolean parallel(long[] a, long[] b) {
 86     return det(a[0], a[1], b[0], b[1]) == 0;
 87   }
 88 
 89   static boolean same(long[] a, long[] b) {
 90     return parallel(a, b) && det(a[0], a[2], b[0], b[2]) == 0 && det(a[1], a[2], b[1], b[2]) == 0;
 91   }
 92 
 93   static long det(long a, long b, long c, long d) {
 94     return a * d - c * b;
 95   }
 96 
 97   static Point2D.Double intersect(long[] a, long[] b) {
 98     long det = det(a[0], a[1], b[0], b[1]);
 99     if (det != 0) {
100       double x = -det(a[2], a[1], b[2], b[1]);
101       double y = -det(a[0], a[2], b[0], b[2]);
102       return new Point2D.Double(x / det, y / det);
103     }
104     return null;
105   }
106 }