[PKU2318]TOYS

题目大意就是说一个矩形被不相交线段分割成了几块,有些点落在里面(不会落在线段上),统计每一个区域里面有多少个点。

这题就是叉积的典型应用。因为线段不会相交,所以一个点在哪个区间里面,只需要知道它在哪两条中间就好了。朴素的做法就是枚举线段,这样需要O(nm)的时间。其实可以用二分优化,不断往右找,直到找到一条在当前线段的右边的最靠左边线段,那么这个点就在这个线段和上一条线围成的块里了,复杂度优化到O(nlogm)。
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
#include <cstring>
#include <iostream>
using namespace std;

struct Point
{
  int x, y;
  Point(const int& _x = 0, const int& _y = 0): x(_x), y(_y) { }
};
int n, m, count[5002];
Point p, UpLeft, DownRight;
pair<int, int> l[5002];
inline int CrossProduct(const Point &A, const Point &B, const Point &C, const Point &D)
{
  const int x1 = B.x-A.x, y1 = B.y-A.y;
  const int x2 = D.x-C.x, y2 = D.y-C.y;
  return x1*y2-y1*x2;
}
int main()
{
  ios::sync_with_stdio(false);
  while (cin >> n, n)
  {
    memset(count, 0, sizeof(count));
    cin >> m >> UpLeft.x >> UpLeft.y >> DownRight.x >> DownRight.y;
    for (int i = 0; i < n; ++i)
      cin >> l[i].first >> l[i].second;
    l[n].first = l[n].second = DownRight.x;

    while (m--)
    {
      cin >> p.x >> p.y;
      int lef = -1, rig = n+2;
      while (rig-lef > 1)
      {
        int mid = (lef+rig)>>1;
        Point p1(l[mid].first, UpLeft.y);
        Point p2(l[mid].second, DownRight.y);
        if (CrossProduct(p1, p2, p1, p) > 0)
          lef = mid;
        else
          rig = mid;
      }
      ++count[rig];
    }
    for (int i = 0; i <= n; ++i)
      cout << i << ": " << count[i] << endl;
    cout << endl;
  }
}

Comments