首页 > 代码库 > POJ 2954 Triangle (皮克定理, 三角形叉乘求面积)

POJ 2954 Triangle (皮克定理, 三角形叉乘求面积)

2024-11-26 14:59:38   204人阅读


Triangle
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 5303
Accepted: 2297

Description

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).

Input

The input test file will contain multiple test cases. Each input test case consists of six integersx1, 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 withx1 =  y1 = x2 = y2 =x3 = y3 = 0 and should not be processed.

Output

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

Sample Input

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

Sample Output

0
6

Source

Stanford Local 2004

题目链接：http://poj.org/problem?id=2954

题目大意：给出三个点，求这三点组成的三角形中整数坐标点得个数

题目分析：利用皮克定理，S=a+b/2-1，其中a表示多边形内部的点数，b表示多边形边界上的点数，s表示多边形的面积
则a = S + 1 - b/2
还有两个常用公式：
1.给出三点(x1, y1) (x2, y2) (x3, y3)求三角形面积，用海伦公式太麻烦，现给出叉乘公式 S = abs(((x2-x1) * (y3-y1) - (x3-x1) * (y2-y1)) / 2)，abs为取绝对值
2.给出两点(x1, y1) (x2, y2)，求这两点组成得线段间整数坐标点得个数 b = gcd(abs(x1 - x2)，abs(y1 - y2))，gcd为最大公约数
有了这两个公式这天就好解决了，本题还有一个问题就是输入不能已(x1 + y1 + x2 + y2 + x3 + y3) != 0判断，例如1 1 -2 3 4 -7答案是8

#include <cstdio>
#include <cmath>

int abs(int x)
{
    return x > 0 ? x : -x;
}

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;  
}

int main()
{
    int x1, y1, x2, y2, x3, y3;
    while(scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3) != EOF)
    {
        if(x1 == 0 && y1 == 0 && x2 == 0 && y2 == 0 && x3 == 0 && y3 == 0)
            break;
        int x12 = abs(x1 - x2);
        int y12 = abs(y1 - y2);
        int x13 = abs(x1 - x3);
        int y13 = abs(y1 - y3);
        int x23 = abs(x2 - x3);
        int y23 = abs(y2 - y3);
        printf("%d\n", abs(((x2-x1) * (y3-y1) - (x3-x1) * (y2-y1)) / 2) + 1 - (gcd(x12,y12) + gcd(x13,y13) + gcd(x23,y23)) / 2);
    }
}


POJ 2954 Triangle (皮克定理, 三角形叉乘求面积)


联系
我们