POJ 2954 – Triangle [几何/Pick定理]

Link

传送门

Problem

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

Mean

给你一个三角形(三点均为整点),让你求三角形内部有多少个整数点,不包括边上和角上的点。

Analysis

比赛的时候不知道有一个Pick定理,现在知道了,直接套模板好了。

可以将所有变量同时扩大两倍,这样就保证所有值为小数,没有误差。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0):x(x), y(y) {}
    Point operator + (Point rhs) const { return Point(x+rhs.x, y+rhs.y); }
    Point operator - (Point rhs) const { return Point(x-rhs.x, y-rhs.y); }
    int dot(Point rhs) { return x * rhs.x + y * rhs.y; }
    int cross(Point rhs) { return x * rhs.y - y * rhs.x; }
};

Point tr[5];

int triArea(Point a, Point b, Point c) {
    return abs((b-a).cross(c-a));
}

int borderIntPointNum() {
    int num = 0;
    tr[3].x = tr[0].x;
    tr[3].y = tr[0].y;
    for(int i = 0; i < 3; ++i) {
        num += __gcd(abs(int(tr[i+1].x - tr[i].x)), abs(int(tr[i+1].y - tr[i].y)));
    }
    return num;
}

int insideIntPointNum() {
    return triArea(tr[0], tr[1], tr[2]) + 2 - borderIntPointNum();
}

int main()
{
    while(true) {
        bool flag = false;
        for(int i = 0; i < 3; ++i) {
            scanf("%d%d", &tr[i].x, &tr[i].y);
            if(tr[i].x || tr[i].y) flag = true;
        }
        if(!flag) break;
        printf("%d\n", insideIntPointNum() >> 1);
    }
    return 0;
}

欢迎留言