首页 > 专题系列 > Java解POJ > POJ 2954 Triangle [解题报告] Java
2013
11-12

POJ 2954 Triangle [解题报告] Java

Triangle

问题描述 :

A lattice point is an ordered pair (x, y) where x and y are both integers. Given the coordinates of the vertices of a triangle (which happen to be lattice points), you are to count the number of lattice points which lie completely inside of the triangle (points on the edges or vertices of the triangle do not count).

输入:

The input test file will contain multiple test cases. Each input test case consists of six integers x1, y1, x2, y2, x3, and y3, where (x1, y1), (x2, y2), and (x3, y3) are the coordinates of vertices of the triangle. All triangles in the input will be non-degenerate (will have positive area), and −15000 ≤ x1, y1, x2, y2, x3, y3 ≤ 15000. The end-of-file is marked by a test case with x1y1 = x2 = y2 = x3 = y3 = 0 and should not be processed.

输出:

For each input case, the program should print the number of internal lattice points on a single line.

样例输入:

0 0 1 0 0 1
0 0 5 0 0 5
0 0 0 0 0 0

样例输出:

0
6

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
class Point{
	int x,y;
}
public class Main {
	
	static Point triangle[] = new Point[3];
	static int GCD(int a,int b){
		if(b==0) return a;
		return GCD(b,a%b);
	}
	static int area(Point a,Point b,Point c){
		return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
	}
	static int solve(){
		int ans=0,i=0;
		int area = area(triangle[0],triangle[1],triangle[2]);
		i += node_in_line(triangle[0],triangle[1]);
		i += node_in_line(triangle[1],triangle[2]);
		i += node_in_line(triangle[0],triangle[2]);
		if(area< 0) area = -area;
		ans = (area-i+2)/2;
		return ans;
	}
	static int node_in_line(Point a,Point b){
		int x,y;
		x = a.x-b.x;
		if(x< 0) x = -x;
		y = a.y-b.y;
		if(y< 0) y = -y;
		if(x==0) return y;
		if(y==0) return x;
		return GCD(x,y);
	}
	public static void main(String[]args) throws Exception{
		
		int i,j;
		//Scanner cin = new Scanner(new FileInputStream("input.txt"));
		Scanner cin = new Scanner(System.in);
		for(i=0;i< 3;++i) triangle[i] = new Point();
		while(true){
			for(i=j=0;i< 3;++i){
				triangle[i].x = cin.nextInt();
				triangle[i].y = cin.nextInt();
				if(triangle[i].x!=0) j=1;
				if(triangle[i].y!=0) j=1;
			}
			if(j==0) break;
			
			System.out.println(solve());
		}
	}
}

  1. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.