[BZOJ1573][Usaco2009 Open]牛绣花cowemb

一开始想到了在两条之间范围内的直线焦点数，也就是逆序对。但是题目给的是圆，不像两条直线那样可以直接确定在两条直线上的位置，也就无法逆序对……

但是，跟上面有点类似的，这题也可以将直线转化掉。

考虑每一条跟圆相交的直线，它必与圆交于两点，相切的话当作两个相同的点。那么，一条直线就变成了圆上的一段弧。至于是优弧还是劣弧并不重要，原因如下：考虑两条与圆相交的直线A和B，那么把它们两个端点按照极角排序后的顺序只有两种（可以移动）：ABAB或者ABBA。显然，只有当出现ABAB这种情况，也就是两条弧相交且不包含时，两条直线相交。那么回到优弧和劣弧的问题上，假设B是优弧还是劣弧确定了，且A的劣弧与B的弧相交，那么A的优弧必与B的弧相交。因此，优弧或者劣弧并不影响结果。

现在，我们就把问题转化成：在数轴上有一些长度不等的线段，问有多少对线段相交且不包含。

解决方法：

称某条直线与圆的2个交点中，按照极角排序后较小的为左括号，较大的为右括号。设数组C[]，初始化为0。 
for i ∈ 所有交点
  if i 为某条直线L的左括号
    C[i] = 1
  else
    j = i对应的该条直线的左括号
    ans += C[j+1]+...+C[i]
    C[j] = 0

实际上，每一次遇到右括号，就统计出当前直线L与在其左端点以后的直线的相交次数，当所有点做完之后，C[]数组全部为0，ans即为所求的交点数量。

可以用树状数组或者线段树维护区间和。 
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

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

struct Point
{
  long double angle;
  int belong;
  Point(const long double a, const int b): angle(a), belong(b) { }
};
inline bool operator<(const Point& lhs, const Point& rhs) { return rhs.angle > lhs.angle; }
std::vector<Point> v;
int n, d, C[100001], visited[50000];
int Query(int x)
{
  int res = 0;
  while (x)
  {
    res += C[x];
    x -= x&-x;
  }
  return res;
}
void Add(int x, const int delta)
{
  while (x <= 2*n)
  {
    C[x] += delta;
    x += x&-x;
  }
}
int main()
{
  scanf("%d%d", &n, &d);
  for (int i = 0; i < n; ++i)
  {
    long long a, b, c;
    scanf("%lld%lld%lld", &a, &b, &c);
    const long long tmp = a*a+b*b;
    const long long delta2 = d*d*tmp-c*c;
    if (delta2 > 0)
    {
      const long double delta = sqrt(delta2), tmp2 = tmp;
      const long double
        x1 = (a*c+b*delta)/tmp2,
        x2 = (a*c-b*delta)/tmp2,
        y1 = (b*c-a*delta)/tmp2,
        y2 = (b*c+a*delta)/tmp2;
      v.push_back(Point(atan2(y1, x1), i));
      v.push_back(Point(atan2(y2, x2), i));
    }
  }
  std::sort(v.begin(), v.end());

  long long ans = 0;
  for (std::vector<Point>::size_type i = 0; i < v.size(); ++i)
    if (visited[v[i].belong])
    {
      ans += Query(i+1)-Query(visited[v[i].belong]+1);
      Add(visited[v[i].belong]+1, -1);
    }
    else
    {
      visited[v[i].belong] = i;
      Add(i+1, 1);
    }
  printf("%lld", ans);
}

Comments