Toy Storage
计算几何基础题 题意大致是：一个长方格，被分成好几个空间，然后再给你一堆点，问你每个空间里面有多少个点。
脑洞：题意里面说了，这些分割空间的线没有交点，我们把他们用两个数组存一下，排个序。 如何判断点是在哪个格子呢？ 将这个点和分割线的两端连线，形成两个向量（注意向量的方向，为该点指向分割线的两端）， 如果这两个向量的叉积为负数（注意叉乘时两个向量的前后位置），则说明左边。 至于怎么判断在两个分割线之间，就用这个方法。
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #define len 100010 using namespace std; int n, m; double x1, y1, x2, y2; double _x[len], _y[len]; int num[len], _num[len]; double cross(double ax, double ay, double bx, double by){ return ax * by - ay * bx; } void Init(){ memset(_x, 0, sizeof (_x)); memset(_y, 0, sizeof (_y)); memset(num, 0, sizeof (num)); memset(_num, 0, sizeof (_num)); } bool cmp(const double& a, const double& b){ return a < b; } int main(){ while (~scanf("%d", &n)){ if (!n) break; scanf("%d%lf%lf%lf%lf", &m, &x1, &y1, &x2, &y2); Init(); for (int i=0; i<n; i++) scanf ("%lf%lf", &_x[i], &_y[i]); sort(_x, _x+n, cmp); sort(_y, _y+n, cmp); double x, y; for (int i=0; i<m; i++){ scanf("%lf%lf", &x, &y); if (x<x1 || y>y1 || x>x2 || y<y2) continue; int l = 0, r = n-1, mid; while (r >= l){ mid = (l + r) >> 1; // printf ("%d: %f, %f\n",mid, cross(_x[mid]-x, y1-y, _y[mid]-x, y2-y),cross(_x[mid+1]-x, y1-y, _y[mid+1]-x, y2-y)); if(cross(_x[mid]-x, y1-y, _y[mid]-x, y2-y) < 0) r = mid - 1; else l = mid + 1; } num[l] ++; } for (int i=0; i<n+1; i++) if (num[i]) _num[num[i]]++; printf("Box\n"); for (int i=1; i<m+1; i++) if (_num[i]) printf("%d: %d\n", i, _num[i]); } return 0; }