首页 > 专题系列 > Java解POJ > POJ 3429 Geometry with a ruler [解题报告] Java
2013
11-12

POJ 3429 Geometry with a ruler [解题报告] Java

Geometry with a ruler

问题描述 :

Classic geometric construction is based on two instruments: ruler and compass. However, some constructions are possible using only the ruler. Specifically, let us define that if we have a set of N points, we can select two pairs of them, draw a line through each pair, and construct a new point as an intersection of these two lines. New point can then be added to the set as (N + 1)-th point, and the process repeated.

Such geometric constructions are abstract notions, and attempt to verify them with physical pencil and ruler can lead to errors caused by imprecision of these instruments. So you are tasked to write a program that does exact verification.

Your program must read a set of points and a sequence of constructing operations and find out whether the point with coordinates (0, 0) is one of the constructed points. Note that, similar to physical instruments, floating point calculations performed by computers are also imprecise. This should not, of course, alter verification results.

输入:

Input file contains number of points N followed by their integer coordinates x1 y1 x2 y2 … xN yN. Next comes number of construction operations M followed by M quads of integers ai bi ci di, where k-th quad means that a new point is constructed as an intersection of lines containing pairs of points ai, bi and ci, di. Such a point is guaranteed to exist. Constructed point is assigned a number N + k and can be used in following operations.

Constraints

4 ≤ N ≤ 100, 1 ≤ M ≤ 10, −106xi, yi ≤ 106

输出:

Output file must contain a single integer — number of the first operation which constructs a point (0, 0), or 0 (zero), if there is no such operation.

样例输入:

Sample Input 1
4
-1 -1  -2 2   2 2  1 -1
1
1 3 2 4
Sample Input 2
4
-1000 -1000  -2000 2000  2001 2000  1000 -1000
1
1 3 2 4

样例输出:

Sample Output 1
1
Sample Output 2
0

温馨提示:

Bold texts appearing in the sample sections are informative and do not form part of the actual data.

解题代码:

//* @author:alpc12
import java.util.*;
import java.math.*;


public class Main {
	
 int n;

 BigInteger[] x = new BigInteger[115];
 BigInteger[] y = new BigInteger[115];
	
 public class Line {
	BigInteger a, b, c;
 }
	
	
 void run() {
   Scanner cin = new Scanner(System.in);
   BigInteger Zero = BigInteger.ZERO;
   n = cin.nextInt();
   int i;
   for(i = 0; i < n; ++i) {
	x[i] = cin.nextBigInteger();
	y[i] = cin.nextBigInteger();
   }
		
   int m = cin.nextInt(), ok = 0;
   for(i = 0; i < m; ++i) {
	int a, b, c, d;
	a = cin.nextInt();
	b = cin.nextInt();
	c = cin.nextInt();
	d = cin.nextInt();
	--a; --b; --c; --d;
	Line l1 = new Line(), l2 = new Line();
	l1.a = y[b].subtract(y[a]);
	l1.b = x[a].subtract(x[b]);
	l1.c = (l1.a.multiply(x[a])).add(l1.b.multiply(y[a]));
			
	l2.a = y[d].subtract(y[c]);
	l2.b = x[c].subtract(x[d]);
	l2.c = (l2.a.multiply(x[c])).add(l2.b.multiply(y[c]));
			
	BigInteger det = (l1.a.multiply(l2.b)).subtract((l2.a.multiply(l1.b)));
	BigInteger sx = (l2.b.multiply(l1.c)).subtract((l1.b.multiply(l2.c)));
	BigInteger sy = (l1.a.multiply(l2.c)).subtract((l2.a.multiply(l1.c)));
	int j;
	for(j = 0; j < n; ++j) {
		x[j] = x[j].multiply(det);
		y[j] = y[j].multiply(det);
	}
	if(sx.compareTo(Zero) == 0 && sy.compareTo(Zero) == 0) {
		if(ok == 0)
			ok = i+1;
	}
	x[n] = sx;
	y[n] = sy;
	n++;
    }
    System.out.println(ok);
   }

	public static void main(String[] args) {
		new Main().run();

	}

}