Triangle
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
Source
题目类型：格点多边形(pick定理)
算法分析：由pick定理可知，格点多边形内部的格点数为：b = (res * 2 - a + 2) / 2。res * 2可以用叉乘计算，a可以用gcd计算
|
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
/************************************************* Author :supermaker Created Time :2016/1/28 15:05:47 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; struct Point { LL x, y; Point () {} Point (LL xx, LL yy) : x (xx), y (yy) {} Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } LL operator ^ (const Point &a) const { return x * a.y - y * a.x; } LL operator * (const Point &a) const { return x * a.x + y * a.y; } }; Point p[6]; LL mabs (LL val) { if (val < 0) return -val; return val; } LL gcd (LL a, LL b) { if (b == 0) return a; else return gcd (b, a % b); } int main() { //CFF; //CPPFF; while (1) { bool is_zero = true; for (int i = 0; i < 3; i++) { scanf ("%lld%lld", &p[i].x, &p[i].y); if (p[i].x != 0 || p[i].y != 0) is_zero = false; } if (is_zero) break; LL res = 0, cnta = 0; for (int i = 0; i < 3; i++) { res += p[i] ^ p[(i+1)%3]; cnta += gcd (mabs (p[i].x - p[(i+1)%3].x), mabs (p[i].y - p[(i+1)%3].y)); } res = mabs (res); printf ("%lld\n", (res - cnta + 2) / 2); } return 0; } |
- « 上一篇：poj1265
- poj2976：下一篇 »