[原创]POJ 2954 Triangle [PICK公式+GCD]【计算几何】

2016-04-12 14:03:33 Tabris_ 阅读数：505

博客爬取于2020-06-14 22:44:34
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51132938

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

Triangle
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 5661 Accepted: 2439
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 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 x1 = 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

题目大意 ：
在一个网格上有三个点，求这三个点围城的三角形内部有几个格点（恰好在三角形的边上的格点不算）。

题目思路：
涉及到格点了，很容易先到是PICK公式——S=a/2+b-1。
（Ps :不知道什么是PICK公式的点这里->这里T_T这里）
这是一个PICK公式的逆运用来求b。
转换一下公式即可=>b=(2S-a)/2+1。
本题中要先把每条边上的格点数求出来,其实很简单运用GCD(辗转相除法)即可。设每条边的向量为(x,y)->GCD(x,y)就是这条边上的格点个数-1,很好理解,求得的结果是排除这条边的一个端点的. 而最大公约数实几就证明有几个格点在边上.也就是这个方向的向量中满足两端均在格点上的向量为(x,y)/GCD(x,y),那么GCD(x,y)为几就说明有几个这样的 “单位” 向量.
明白了以上代码实心就好了,

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# include<iostream>
# include<stdio.h>
# include<math.h>
# include<stdlib.h>
using namespace std;

struct point
{
    int x, y;
};

int multi(point &p1, point &p2,point &p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}

int gcd(int x, int y)
{
    if (x==0||y==0)  return max(x,y);
    return gcd(y,x%y);
}

int pick(int area, int num)
{
    return (area - num)/2 + 1;
}

int main()
{
    point one, two, three;
    int x1, x2, x3, y1, y2, y3;
    while (~scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3))
    {
        if(x1==0&&x2==0&&x3==0&&y1==0&&y2==0&&y3==0)   break;
        one.x = x1,one.y = y1,two.x = x2,two.y = y2,three.x = x3,three.y = y3;

        int area=multi(one,two,three);
        if (area<0)  area=-area;
        int num = gcd(abs(one.x - two.x),abs(one.y - two.y));
        num += gcd(abs(two.x - three.x),abs(two.y - three.y));
        num += gcd(abs(three.x - one.x),abs(three.y - one.y));
        cout<<pick(area,num)<<endl;
    }
    return 0;
}