统计三角形内点的个数。
如下图所示，P(ABC)=|P(AB)+P(BC)-P(AC)|。P(AB)代表线段AB上方的点的个数
1 #include <string.h> 2 #include <stdio.h> 3 #include <algorithm> 4 #define MAXN 105 5 typedef long long LL; 6 struct pnt{ 7 LL x, y; 8 bool operator < (const pnt &p) const {return x < p.x;} 9 }pn[MAXN], pm[MAXN*10]; 10 LL xmult(pnt p1, pnt p2, pnt p3) { 11 return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x); 12 } 13 14 int d[MAXN][MAXN], ans, cas = 1, n, m; 15 int main(){ 16 while (scanf("%d%d", &n, &m) != EOF) { 17 for (int i = 0; i < n; i++) scanf("%I64d%I64d", &pn[i].x, &pn[i].y); 18 for (int i = 0; i < m; i++) scanf("%I64d%I64d", &pm[i].x, &pm[i].y); 19 memset(d, 0, sizeof d); ans = 0; 20 std::sort(pn, pn + n); 21 for (int i = 0; i < n; i++) for (int j = i+1; j < n; j ++) for (int k = 0; k < m; k++) 22 if (pn[i].x <= pm[k].x && pm[k].x < pn[j].x && xmult(pn[i], pn[j], pm[k]) < 0) d[i][j]++; 23 for (int i = 0; i < n; i++) for (int j = i+1; j < n; j ++) for (int k = i+1; k < j; k++) 24 if (std::abs(d[i][j]-d[i][k]-d[k][j])&1) ans++; 25 printf("Case %d: %d\n", cas++, ans); 26 } 27 return 0; 28 }