poj2954 Triangle——pick定理

poj2954 Triangle——pick定理

题意：给定一个三角形，三角形的三个点都是整数点，问有多少个整数点严格在三角形内部

思路：典型的pick定理题目，公式为s=a+b/2-1，s为整数顶点的多边形面积，a为它内部的整数点， b为它边上的整数点（包括顶点），那么题目要求的其实是b=(2*s+2-a)/2

s可以通过向量的叉积运算得到，a可以通过gcd得到，两个点形成的线段包含的整数点为它们横坐标差值的绝对值和纵坐标差值的绝对值的gcd-1，注意特判一下两个差值都为0的情况

#include #include #include #include #include using namespace std;typedef long long ll;struct Point { ll x, y; Point(ll xx = 0, ll yy = 0) : x(xx), y(yy) {}}p[3];Point operator + (Point a, Point b) { return Point(a.x+b.x, a.y+b.y); }Point operator - (Point a, Point b) { return Point{a.x-b.x, a.y-b.y}; }ll Cross(Point a, Point b) { return a.x*b.y - a.y*b.x; }ll mabs(ll x) { return x < 0 ? -x : x;}ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y);}ll Area(Point a, Point b, Point c) { return mabs(Cross(a-c, b-c));}ll cnt(Point a, Point b) { ll x = mabs(a.x-b.x), y = mabs(a.y-b.y); if (x == 0 && y == 0) return 0; else return gcd(x, y)-1;}int main() { while (~scanf("%lld%lld%lld%lld%lld%lld", &p[0].x, &p[0].y, &p[1].x, &p[1].y, &p[2].x, &p[2].y)) { bool ok = true; for (int i = 0; i < 3; i++) { if (p[i].x != 0 || p[i].y != 0) { ok = false; break; } } if (ok) break; ll t = 3LL + cnt(p[0], p[1]) + cnt(p[1], p[2]) + cnt(p[0], p[2]); printf("%lld\n", ( Area(p[0], p[1], p[2]) + 2 - t) / 2); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。