求点阵上取3点组成的三角形内部的点数,利用PICK定理
PICK定理:平面上以格子点为顶点的简单多边形的面积=边上的点数/2+内部的点数-1
这样只要利用叉积求出三角形面积,在利用gcd求出边上点数,就可以计算了
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct Point { int x, y; Point() {} Point(int x, int y) { this->x = x; this->y = y; } void read() { scanf("%d%d", &x, &y); } } p[5]; typedef Point Vector; Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); } Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); } int Cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x;} //叉积 int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b); } int x1, y1, x2, y2, x3, y3; int cal(Point a, Point b) { int dx = a.x - b.x; if (dx < 0) dx = -dx; int dy = a.y - b.y; if (dy < 0) dy = -dy; return gcd(dx, dy); } int main() { while (~scanf("%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3)) { if (!x1 && !y1 && !x2 &&!y2 && !x3 && !y3) break; p[0] = Point(x1, y1); p[1] = Point(x2, y2); p[2] = Point(x3, y3); int d = 0; d = cal(p[0], p[1]) + cal(p[1], p[2]) + cal(p[2], p[0]); int ans = Cross(p[1] - p[0], p[2] - p[0]); if (ans < 0) ans = -ans; printf("%d\n", (ans - d + 2) / 2); } return 0; }