In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. In the question here, we are concerned with the following, related problem: First n straws are dumped on the table. Next, for every pair of straws, we want to determine if the straws are connected by a path of touching straws. In other words, given a list of the endpoints for n > 1 straws (as if they were dumped on a large piece of graph paper), determine all the pairs of straws that are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws. Give an algorithm to compute all the pairs of straws that are connected.
Here is some additional information that you can use:
i. As a basic step you need to determine whether two straws directly touch (intersect), i.e., whether straw ab with end points a and b intersects with straw cd (with end points c and d).
ii. To get full credit also explain how the elementary step i) can be done. If you cannot find an algorithm for this step, assume an O(n 2 ) algorithm and explain how to find all pairs of straws that are connected.
Analyse and explain the worst-case computational complexity of your algorithm in terms of n.

• //jack of straws
  import java.io.FileInputStream;
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.io.PrintWriter;
  import java.io.OutputStreamWriter;
  import java.io.StreamTokenizer;
  
  public class Main {
  private static final boolean DEBUG = false;
  private BufferedReader cin;
  private PrintWriter cout;
  private StreamTokenizer tokenizer;
  private Line[] lines;
  private int n;
  private boolean[][] g;
  
  class Point
  {
  int x, y;
  }
  
  class Line
  {
  Point a, b;
  }
  
  public void init()
  {
  try {
  if (DEBUG) {
  cin = new BufferedReader(new InputStreamReader(
  new FileInputStream("e:\uva_in.txt")));
  } else {
  cin = new BufferedReader(new InputStreamReader(System.in));
  }
  
  tokenizer = new StreamTokenizer(cin);
  cout = new PrintWriter(new OutputStreamWriter(System.out));
  } catch (Exception e) {
  e.printStackTrace();
  }
  }
  
  private String next()
  {
  try {
  tokenizer.nextToken();
  if (tokenizer.ttype == StreamTokenizer.TT_EOF) return null;
  else if (tokenizer.ttype == StreamTokenizer.TT_NUMBER) {
  return String.valueOf((int)tokenizer.nval);
  } else return tokenizer.sval;
  
  } catch (Exception e) {
  e.printStackTrace();
  return null;
  }
  }
  
  public boolean input()
  {
  n = Integer.parseInt(next());
  lines = new Line[n];
  
  for (int i = 0; i < n; i++) {
  lines[i] = new Line();
  lines[i].a = new Point();
  lines[i].a.x = Integer.parseInt(next());
  lines[i].a.y = Integer.parseInt(next());
  lines[i].b = new Point();
  lines[i].b.x = Integer.parseInt(next());
  lines[i].b.y = Integer.parseInt(next());
  }
  
  return true;
  }
  
  private int cross(Point a, Point b, Point c, Point d)
  {
  int x1 = b.x - a.x, y1 = b.y - a.y;
  int x2 = d.x - c.x, y2 = d.y - c.y;
  
  return x1 * y2 - y1 * x2;
  }
  
  
  private boolean intersection(Line l1, Line l2)
  {
  return (Math.max(l1.a.x, l1.b.x) >= Math.min(l2.a.x, l2.b.x) &&
  Math.max(l2.a.x, l2.b.x) >= Math.min(l1.a.x, l1.b.x) &&
  Math.max(l1.a.y, l1.b.y) >= Math.min(l2.a.y, l2.b.y) &&
  Math.max(l2.a.y, l2.b.y) >= Math.min(l1.a.y, l1.b.y) &&
  cross(l1.a, l2.a, l1.a, l1.b) * cross(l1.a, l1.b, l1.a, l2.b) >= 0 &&
  cross(l2.a, l1.a, l2.a, l2.b) * cross(l2.a, l2.b, l2.a, l1.b) >= 0);
  }
  
  private void floyd_warshall()
  {
  for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
  g[i][j] |= g[i][k] & g[k][j];
  }
  }
  }
  }
  
  public void solve(int cas)
  {
  g = new boolean[n][n];
  
  for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
  if (j == i) {
  g[i][j] = g[j][i] = true;
  continue;
  }
  if (intersection(lines[i], lines[j])) {
  g[i][j] = g[j][i] = true;
  }
  }
  }
  
  floyd_warshall();
  
  while (true) {
  int a = Integer.parseInt(next());
  int b = Integer.parseInt(next());
  if (a == 0 && b== 0) break;
  a--; b--;
  if (g[a][b]) cout.println("CONNECTED");
  else cout.println("NOT CONNECTED");
  }
  
  if (cas != 0) cout.println();
  cout.flush();
  }
  
  public static void main(String[] args)
  {
  Main solver = new Main();
  solver.init();
  
  int t = Integer.parseInt(solver.next());
  while (t-- > 0) {
  solver.input();
  solver.solve(t);
  }
  }
  }
  
• 9 years agoHelpfull: Yes(4) No(1)