平面扫描

  1. 扫描的方式一共有两种,一种是横向的沿着一个方向进行扫描统计;
  2. 另外的一种方式就是绕着一个固定的点进行相关的统计

感觉更像是一种思想,找到扫描的策略是更关键的

题目

poj 2932

题意

给你若干个圆,圆之间没有交点, 问有多少个圆不被其他的圆包含

题解

  • 由于没有交点,处理起来相对的容易一些:首先按照x进行排序,然后根据新进来的圆,再按照y的值判断最近的两个圆,看新的圆是否在这两个圆中。找几个特例判断就行了,并不会证明

未验证的代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 4e4+10;
struct Point{
double x, y, r;
}point[maxn];
int n;
bool inside(int id1, int id2){
int dx = point[id1].x-point[id2].x;
int dy = point[id1].y-point[id2].y;
return (dx*dx+dy*dy)<=point[id2].r*point[id2].r;
}
void solve(){
vector<pair<double, int> > events;
for(int i=0; i<n; i++){
events.push_back(make_pair(point[i].x-point[i].r, i));
events.push_back(make_pair(point[i].x+point[i].r, i+n));
}
sort(events.begin(), events.end());
set<pair<double, int> > outer;//记录的是y的值以及圆的序号
vector<int> ans;
for(int i=0; i<2*n; i++){
int id = events[i].second%n;
if(events[i].second<n){
pair<double, int> temp = make_pair(point[id].y, id);
set<pair<double, int> >::iterator it
= outer.lower_bound(temp);
if(it!=outer.end() && inside(id, it->second)) continue;
if(it!=outer.begin() && inside(id, (--it)->second)) continue;
outer.insert(temp);
ans.push_back(id);
}
else{
outer.erase(make_pair(point[id].y, id));
}
}
sort(ans.begin(), ans.end());
int len = ans.size();
for(int i=0; i<len-1; i++){
printf("%d ", ans[i]+1);
}
printf("%d\n", ans[len-1]+1);
}
int main()
{
while(~scanf("%d", &n)){
for(int i=0; i<n; i++){
scanf("%lf%lf%lf", &point[i].r, &point[i].x, &point[i].y);
}
solve();
}
return 0;
}

直线扫描(挑程2里面的题目)

和x轴与Y轴垂直的若干条线段,问交点的个数。

题解

按照一维进行扫描(下面的讲解以扫描线平行于x轴为例)。若扫描线接触到线段的下端点,就将点插入到二叉树中。若遇到了平行于x轴的线,则在二叉树中查找相应线段范围内的点的个数。

未解决的问题

文章目录
  1. 1. 题目
  2. 2. 题意
  3. 3. 题解
    1. 3.1. 未验证的代码
  4. 4. 直线扫描(挑程2里面的题目)
    1. 4.1. 题解
  5. 5. 未解决的问题
{{ live2d() }}