扫描线题目汇总（里面的题解和代码非原创）

转载自：http://blog.csdn.net/accry/article/details/6676009

题意：

原子弹爆炸，一些互不相交的线段，求能辐射到的线段个数（可以将原子弹爆炸点视为泛光源）

分析：

以辐射源为中心对周围的点按照极坐标角度进行排序，然后在极坐标上使用扫描线方法。
维护一个集合，集合内的元素是与扫描线相交的线段，排序依据是线段与扫描线的交点到辐射源的距离。该集合中的最小元素就是被照射到的线段。

有关容器（set）排序依据的说明：

在扫描线运动前后，如果有两个线段存在于容器中，这两个线段与扫描线的交点到辐射源的距离远近关系不会发生变化。若发生变化，表示扫描线运动范围内两个线段有交点，与题目提供的已知条件不符。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <set>
  5 #include <algorithm>
  6 using namespace std;
  7 #define EPS 1e-8
  8 #define LS0(a) (a << 1)
  9 #define LS1(a) ((a << 1) | 1)
 10 
 11 const int MAXN = 20010;
 12 struct Point { 
 13     double x, y;
 14     Point(double _x = 0.0, double _y = 0.0): x(_x), y(_y) {}
 15     Point operator + (const Point &b) const {
 16         return Point(x + b.x, y + b.y);
 17     }
 18     Point operator - (const Point &b) const {
 19         return Point(x - b.x, y - b.y);
 20     }
 21     double operator ^ (const Point &b) const {
 22         return x * b.y - y * b.x;
 23     }
 24     bool operator < (const Point &b) const {  //逆时针
 25         return x * b.y < y * b.x;
 26     }
 27     void input() {
 28         scanf("%lf%lf", &x, &y);
 29     }
 30     double diso() {
 31         return sqrt(x * x + y * y);
 32     }
 33 
 34 }cur,ps[MAXN];
 35 
 36 Point lnlncross_pt(Point aa, Point ad, Point ba, Point bd) { // 求直线交点
 37     ad = ad - aa;
 38     bd = bd - ba;
 39     double tmp = bd ^ ad;
 40     return Point(
 41         (ad.x * bd.x * (ba.y - aa.y) + aa.x * bd.x * ad.y - ba.x * ad.x * bd.y) / tmp,
 42         (ad.y * bd.y * (aa.x - ba.x) + ba.y * ad.y * bd.x - aa.y * bd.y * ad.x) / tmp);
 43 }
 44 
 45 struct Item { // 扫描线的点类型
 46     Point *u, *v;
 47     int type; // 1: 线段起点; 0: 线段终点;
 48     int sgid; // 线段序号
 49     Item(Point *_u = NULL, Point *_v = NULL, int _ty = 0, int _id = 0)
 50         : u(_u), v(_v), type(_ty), sgid(_id) {}
 51     bool operator < (const Item &b) const {
 52         if(u == b.u && v == b.v)
 53             return false;
 54         Point au = lnlncross_pt(Point(0.0, 0.0), cur, *u, *v);
 55         Point bu = lnlncross_pt(Point(0.0, 0.0), cur, *b.u, *b.v);
 56         return au.diso() < bu.diso();
 57     }
 58 
 59 }item[MAXN];
 60 
 61 bool flag[MAXN];
 62 set<Item> Scan;
 63 
 64                     
 65 bool cmp(const Item &a, const Item &b) { //极角排序 从-PI到-PI内 
 66         return atan2(a.u->y, a.u->x) < atan2(b.u->y, b.u->x);
 67 
 68 }
 69 
 70 void inputps(int n) {
 71     Point src, a, b;
 72     src.input();
 73     for(int i = 0; i < n; ++i) {
 74         // 读取线段并求得相对于光源的坐标
 75         a.input(); a = a - src;
 76         b.input(); b = b - src;
 77         // 保证线段的极角序
 78         if(b < a) swap(a, b);
 79         ps[LS0(i)] = a;
 80         ps[LS1(i)] = b;
 81         item[LS0(i)] = Item(&ps[LS0(i)], &ps[LS1(i)], 0, i);
 82         item[LS1(i)] = Item(&ps[LS1(i)], &ps[LS0(i)], 1, i);
 83     }
 84     sort(item, item + 2 * n, cmp);
 85 }
 86 
 87 
 88 
 89 bool sgcross_with_ax(Item &a) {   //与射线相交判断   good 以前不知道的东西
 90     Point tmp(-1.0, 0.0);
 91     return (*a.u ^ *a.v) * (*a.u ^ tmp) > 0.0
 92         && (*a.u ^ tmp) * (tmp ^ *a.v) > 0.0;
 93 }
 94 
 95 
 96 
 97 int main() {
 98     int n;
 99     while(scanf("%d", &n) != EOF) {
100         inputps(n);
101         memset(flag,0,sizeof(flag));
102         // 初始化极角扫描器  初始射线向量为（-1.0，0)
103         Scan.clear();
104         for(int i = 0; i < 2 * n; ++i) {
105                 cur = *item[i].u;
106             if(item[i].type == 1 && sgcross_with_ax(item[i]))
107                 Scan.insert(item[i]);
108         }
109         // 极角扫描
110         for(int i = 0; i < 2 * n; ++i) {
111                 cur = *item[i].u;
112             if(item[i].type == 1)
113                 Scan.insert(item[i]);
114             else
115                 Scan.erase(Item(item[i].v, item[i].u, 1, item[i].sgid));
116             if(!Scan.empty())
117                 flag[Scan.begin()->sgid] = true;
118         }
119         int ans = 0;
120         for(int i = 0; i < n; ++i)
121             if(flag[i])ans ++;
122         printf("%d
", ans);
123     }
124     return 0;
125 
126 }

hdu 3124 Moonmist （圆的扫描）

转自：http://blog.sina.com.cn/s/blog_64675f540100o02x.html

题目描述：

给你n（50000）个不相交的圆，告诉你各个圆的xy坐标和半径，问你最近的两个圆之间的距离（两圆心之间的距离减去各自的半径）

解题报告：

暴力的做法扫描任意两圆之间的最近距离，取最小值，n^2复杂度，超时。

正解为：

二分枚举每个圆半径的增量mid。

那么此时的每个圆i的半径为R[i] + mid（R[i]为这个圆原来的半径），对于这组新的半径，如果在n个圆中存在两个圆相交，那么就说明mid偏大，反之，如果不存在，则mid偏小。这样就可以达到二分的目的。

二分的复杂度可以在此近似为logn，那么问题转化为：怎样在O(n)或者O(nlogn)的时间内检测出n个圆内是否存在相交的情况，答案是“扫描线”。

常见的扫描线通常利用在正方形的各种检测和求和：在x方向从左到右扫描，y方向用set或者线段树维护当前的线段位置即可，如果覆盖相同的线段即相交。

如下：

从左到右依次扫描竖直的四条线段ABCD，

A：插入1~3的线段

B：插入0~2的线段，和现存的1~3线段冲突，所以存在相交情况。

C：删除1~3线段

D：删除0~2线段

但是现在是圆形，从左到右扫描，一个圆的开始位置和结束位置之间，这个圆的纵向线段长度是在不断变化的，需要另外的一种方法。

这里采用两条扫描线，均是从左向右，每次检测的是这两条扫描线之间的圆的碰撞情况。

如图：

第一条扫描线从左往右依次是每个圆的左边界，即竖直线L1，L2，L3。

第二条扫描线从左往右依次是每个圆的右边界，即竖直线R1，R2，R3。

两条扫描线均是从最左边的L1和R1开始，保证L扫描线的x坐标永远小于R扫描线的x坐标即可。扫描流程如下，假设有n个圆，i为Li，j为Rj：

i = j = 1

while(i <= n or j <= n)

{

if(i == n + 1) 删除圆j，j++;

else if (j == n + 1) 插入圆i，检测圆i的圆心和y方向相邻两圆的碰撞情况。i++。

else if (i <= n and Li 在Ri的左边)

插入圆i，检测圆i的圆心和y方向相邻两圆的碰撞情况。i++。

else 删除圆j，j++;

}

简要解释如下：

While中有4个分支

前两个是边界情况，很容易理解。

第三个是L扫描线的推进，即插入圆。

第四个条件：由于只需检测Li 和 Rj两条扫描线之间的圆的相交情况，所以，Li之前的圆都需要删除

当扫描线为Li和Rj时，已经插入的圆都是x方向起点小于等于Li，x方向终点大于等于Rj，即在Li和Rj之间是连续不间断的，所以只需检测插入圆的圆心的上下相邻的两个即可，不可能跳跃。即假设圆心位置从下到上一次编号1~m，那么插入圆x后，不可能出现x和x+2相交而不和x+1相交的情况（应为在Li和Rj之间是连续的）。

至于检测的方法就是线段树或者set了。

上图的扫描线过程是：

初始为L1,R1

L1 < R1, 插入圆A，检测无碰撞，变为L2，R1

L2 < R1, 插入圆B，检测无碰撞，变为L3, R1

L3 > R1, 删除圆B，变为L3，R2

L3 < R2，插入圆C，检测到碰撞，结束

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<set>
  5 #include<algorithm>
  6 #include<cmath>
  7 using namespace std;
  8 #define size 50000
  9 #define eps 1e-8
 10 #define sqr(x) ((double)(x) * (x))
 11 int Left[size], Right[size], Up[size], up_rank[size];
 12 int X[size], Y[size], R[size];
 13 int t, n;
 14 double mid;
 15 set<int> mytree;
 16 typedef set<int>::iterator it;
 17 bool cmp_left(const int &a, const int &b){return (X[a] - R[a] < X[b] - R[b]);}
 18 bool cmp_right(const int &a, const int &b){return (X[a] + R[a] < X[b] + R[b]);}
 19 bool cmp_up(const int &a, const int &b){if (Y[a] == Y[b]) return X[a] < X[b]; else return Y[a] < Y[b];}
 20 bool collid(int a, int b)
 21 {
 22     a = Up[a];
 23     b = Up[b];
 24     return (sqr(X[a] - X[b]) + sqr(Y[a] - Y[b]) - sqr(R[a] + R[b] + mid + mid) <= 0);
 25 }
 26 bool insert(int &id)
 27 {
 28     it i = mytree.insert(id).first;
 29     if (i != mytree.begin())
 30     {
 31         if (collid(id, *--i))
 32             return false;
 33         ++i;
 34     }
 35     if (++i != mytree.end())
 36     {
 37         if (collid(id, *i))
 38             return false;
 39     }
 40     return true;
 41 }
 42 bool remove(int v) {
 43     it i = mytree.find(v);
 44     if (i != mytree.begin() && i != --mytree.end()) {
 45         int a = *--i;
 46         ++i;
 47         int b = *++i;
 48         if (collid(a, b)) {
 49             return false;
 50         }
 51     }
 52     mytree.erase(v);
 53     return true;
 54 }
 55 
 56 bool judge()
 57 {
 58     mytree.clear();
 59     int l = 0, r = 0;
 60     while(l < n || r < n)
 61     {
 62         if (r == n
 63         ||l != n && (X[Right[r]] + R[Right[r]] + mid) - (X[Left[l]] - R[Left[l]] - mid) >= 0)
 64         {
 65             if (!insert(up_rank[Left[l++]])) return true;
 66         }
 67         else if (!remove(up_rank[Right[r++]]))
 68             return true;
 69     }
 70     return false;
 71 }
 72 double jeogia()
 73 {
 74     for(int i = 0; i < n; i++)
 75         Left[i] = Right[i] = Up[i] = i;
 76     sort(Left, Left + n, cmp_left);
 77     sort(Right, Right + n, cmp_right);
 78     sort(Up, Up + n, cmp_up);
 79     for(int i = 0; i < n; i++)
 80         up_rank[Up[i]] = i;
 81     double s = 0, t = sqrt(sqr(X[0] - X[1]) + sqr(Y[0] - Y[1])) - R[0] - R[1];
 82     while(t - s >= eps)
 83     {
 84         mid = (s + t) * 0.5; //mid 为各个圆需要加上的半径长度
 85         if (judge()) t = mid;//是否有圆相交
 86         else s = mid;
 87     }
 88     return t + s;
 89 }
 90 int main()
 91 {
 92     scanf("%d", &t);
 93     while(t-- && scanf("%d", &n))
 94     {
 95         for(int i = 0; i < n; i++)
 96             scanf("%d%d%d", &X[i], &Y[i], &R[i]);
 97         printf("%.6f
", jeogia());
 98     }
 99     return 0;
100 }

hdu 4629 Burning （覆盖次数1——n的面积）

转载自：http://www.cnblogs.com/Rlemon/archive/2013/07/31/3227729.html

求平面的n个三角形的不同覆盖次数(1 - n)的面积。

题意：给你n个三角形，问覆盖1~n次的面积各是多少，n < 50;

分析：取出所有端点和交点的x坐标，排序，然后对于每一段xi~xi+1的范围的线段都是不相交的，所以组成的

面积要么是三角形，要么是梯形，可以直接用公式算面积，然后对于每一个三角形的线段都标记该段对于

从下往上的扫描线来说是入边还是出边，然后就可以直接计算出这块面积被覆盖了几次；如入边加1，出边减一

下图，黄色表示覆盖次数；

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 #include<cstdlib>
  8 #define pbk push_back
  9 using namespace std;
 10 const int N = 25050+10;
 11 const double eps = 1e-10;
 12 inline double sqr(double x){
 13     return x * x;
 14 }
 15 inline int dcmp(double x){
 16     return x < -eps ? -1 : x > eps;
 17 }
 18 struct Point{
 19     double x,y;
 20     int kind;
 21     Point(){}
 22     Point(double x,double y,int kind = 0):x(x),y(y),kind(kind){}
 23     bool operator < (const Point &p)const{
 24         return dcmp(x - p.x) < 0 || ( dcmp(x - p.x) == 0 && dcmp(y - p.y) < 0 );
 25     }
 26     Point operator - (const Point &p)const{
 27         return Point(x - p.x, y - p.y);
 28     }
 29     Point operator + (const Point &p)const{
 30         return Point(x + p.x, y + p.y);
 31     }
 32     Point operator * (const double &k)const{
 33         return Point (x*k , y*k);
 34     }
 35     Point operator / (const double &k)const{
 36         return Point (x/k, y/k);
 37     }
 38     double operator * (const Point &p)const{
 39         return x * p.y - y * p.x;
 40     }
 41     double operator / (const Point &p)const{
 42         return x * p.x + y * p.y;
 43     }
 44     void input(){
 45         scanf("%lf%lf",&x,&y);
 46     }
 47     void ot(){
 48         printf("%lf %lf
",x,y);
 49     }
 50 };
 51 struct Line{
 52     Point a,b;
 53     int kind;
 54     Line (){}
 55     Line (Point a,Point b,int kind = 0):a(a),b(b),kind(kind){}
 56     double operator * (const Point &p)const{
 57         return ( b - a ) * ( p - a );
 58     }
 59     double operator / (const Point &p)const{
 60         return ( p - a) / ( p - b);
 61     }
 62     bool parallel(const Line &v){
 63         return !dcmp( ( b - a ) * ( v.b - v.a ) ); 
 64     }
 65     int LineCrossLine(const Line &v){
 66         if ( (*this).parallel(v) ){
 67             return ( dcmp( v * a ) == 0);
 68         }return 2;
 69     }
 70     int SegCrossSeg(const Line &v){
 71         int d1 = dcmp( (*this) * v.a);
 72         int d2 = dcmp( (*this) * v.b);
 73         int d3 = dcmp( v * a);
 74         int d4 = dcmp( v * b);
 75         if ( ( d1 ^ d2 ) == -2 && ( d3 ^ d4 ) == -2 ) return 2;
 76         return ( ( d1 == 0 && dcmp( (*this) / v.a ) <= 0 )
 77             ||   ( d2 == 0 && dcmp( (*this) / v.b ) <= 0 )
 78             ||   ( d3 == 0 && dcmp( v / a ) <= 0 )
 79             ||   ( d4 == 0 && dcmp( v / b ) <= 0 )
 80             );
 81     }
 82     Point CrossPoint(const Line &v){
 83         double s1 = v * a, s2 = v * b;
 84         return ( a * s2 - b * s1) / (s2 - s1);
 85     }
 86     void input(){
 87         a.input(); b.input();
 88     }
 89     void ot(){
 90         a.ot(); b.ot();
 91     }
 92 
 93 };
 94 
 95 int n,poly_n,xn;
 96 vector<double> lx;
 97 vector<Line> line;
 98 double ans[N];
 99 void init(){
100     int sz = line.size();
101     for (int i = 0; i < sz; i++){
102         for (int j = i+1; j < sz; j++){
103             if (line[i].SegCrossSeg(line[j]) == 2){
104                 Point p = line[i].CrossPoint(line[j]);
105                 lx.pbk(p.x);
106             }
107         }
108     }
109     
110     sort(lx.begin(),lx.end());
111     xn = unique(lx.begin(),lx.end()) - lx.begin();
112 }
113 vector<Point> qu[N];
114 void work(){
115     for (int i = 0; i <= n; i++) ans[i] = 0;
116     for (int i = 0; i < xn-1; i++){
117         int k = 0;
118         for (int j = 0; j+1 < qu[i].size(); j++){
119             k += qu[i][j].kind;
120             ans[ k ] += (lx[i+1] - lx[i]) * (qu[i][j+1].x+qu[i][j+1].y - qu[i][j].x - qu[i][j].y) / 2;        
121         }
122     }
123     for (int i = 1; i <= n; i++) printf("%.10lf
",ans[i]);
124 }
125 void check(){
126     for (int i = 0; i < xn - 1; i++){
127         cout<<qu[i].size()<<" >.<"<<endl;
128         for (int j = 0; j < qu[i].size(); j++){
129             qu[i][j].ot(); cout<<qu[i][j].kind<<endl;
130         }
131     }
132 }
133 void solve(){
134     for (int i = 0; i < xn; i++) qu[i].clear();
135     for (int i = 0; i < line.size(); i++){
136         int j = lower_bound(lx.begin(),lx.begin()+xn,line[i].a.x) - lx.begin();
137         for (; j+1 < xn; j++ ){
138             double l = lx[j], r = lx[j+1];
139             if (dcmp(r - line[i].b.x) > 0) break;
140             Point p1 = line[i].CrossPoint(Line(Point(l,0), Point(l,1)));
141             Point p2 = line[i].CrossPoint(Line(Point(r,0), Point(r,1)));
142             qu[j].pbk(Point(p1.y, p2.y,line[i].kind));
143         }
144     }
145     for (int i = 0; i < xn - 1; i++) sort(qu[i].begin(), qu[i].end());
146 //    check();
147     work();
148 }
149 int main(){
150     int T; scanf("%d",&T);
151     while (T--){
152         scanf("%d",&n);
153         lx.clear(); line.clear();;
154         for (int i = 0; i < n ;i++){
155             Point t[4];
156             for (int j = 0; j < 3; j++ ){
157                 t[j].input(); 
158             }
159             t[3] = t[0];
160             int flag = 1;
161             if (dcmp( (t[1] - t[0])*(t[2] - t[0]) ) == 0) flag = 0;
162         
163             for (int i = 0; i < 3 && flag; i++ ){
164                 lx.pbk(t[i].x);
165                 for (int j = i+1; j < 3; j++){
166                     Line tmp; tmp.a = t[i]; tmp.b = t[j];
167                     if (dcmp( tmp.a.x - tmp.b.x ) > 0) swap(tmp.a, tmp.b);
168                     
169                     Line tmp2 = Line(t[3-i-j], Point(t[3-i-j].x, t[3-i-j].y - 1));
170                     if (tmp.LineCrossLine(tmp2) != 2) continue;
171                     Point tp = tmp.CrossPoint(tmp2);
172                     if (dcmp(tp.y - t[3-i-j].y) < 0) tmp.kind = 1;
173                         else tmp.kind = -1;    
174                     line.pbk(tmp);
175                 }
176             }
177         }
178         init();
179         solve();    
180     }
181     return 0;
182 }

hdu 3255 Farming （矩形体积并）

转载自：http://blog.csdn.net/ivan_zjj/article/details/7741133

题意：

有N块农田，每块农田中种一种作物，每种作物都有一个价格，当在同一区域内种植了两种不同的作物时，作物价格大的生存下来，生命值小的死亡。求最后的所有作物的能买的总钱数。

思路：

扫描线求体积并，和前面的一个求体积交差不多。我们可以将作物的价格看作是立体的高，这样就可以直接枚举Z轴求二维矩形面积并了。本题关键是转化，思路很好。

先将蔬菜价值（即高度）从小到大排序，然后一层一层地开始扫描，计算每层中的面积并，这个就同二维扫描一样。
　　然后再用面积乘以这层的高度，即得到该层的体积并。然后所有层的体积加起来，即为所求。

把价值等价成高，从价格高的开始枚举

假如i的价格>j的价格，先把价格为i的矩形更新到线段树中，然后价格为i的总价值就是面积（S1）*价格i

然后对于价格j，把i和j价格的矩形都更新到线段树中，然后此时属于j的总价值就是现在的(总面积(S2)-S1)*j；

想象一下长方体，交错在一次，有高有低，怎么求出整个立体形的体积）

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<algorithm>
  4 int N , M ;
  5 int h[5] ;
  6 const int MAXN = 30010 ;
  7 struct point{
  8     int x, y ;
  9     void get(){
 10         scanf("%d %d",&x,&y) ;
 11     }
 12 };
 13 struct Node{
 14     point p1 , p2 ;
 15     int h;
 16 }p[MAXN] ;
 17 
 18 struct Seg{
 19     int l ,r , h , s ;
 20     Seg(){}
 21     Seg(int a, int b ,int c, int d)
 22     :l(a) , r(b) , h(c) , s(d){}
 23     bool operator<(const Seg& cmp) const{
 24         return h < cmp.h ;
 25     }
 26 }pp[MAXN<<1] ;
 27 
 28 int x[MAXN<<1] ;
 29 
 30 int find(int val , int l, int r){
 31     while( l<r ) {
 32         int mid = (l + r)>> 1;
 33         if( x[mid] < val )  l = mid + 1 ;
 34         else        r = mid ;
 35     }
 36     return l ;
 37 }
 38 
 39 int col[MAXN<<3] , sum[MAXN<<3] ;
 40 
 41 void pushup(int l, int r, int idx){
 42     if( col[idx] )  sum[idx] = x[r+1] - x[l] ;
 43     else if( l == r )  sum[idx] = 0 ;
 44     else{
 45         sum[idx] = sum[idx<<1] + sum[idx<<1|1] ;
 46     }
 47 }
 48 
 49 void update(int l, int r, int idx, int a , int b , int v){
 50     if(l==a && b==r){
 51         col[idx] += v ;
 52         pushup(l , r , idx);
 53         return ;
 54     }
 55     int mid = (l + r)>> 1;
 56     int ls = idx<<1 , rs = idx<<1|1 ;
 57     if( b<=mid )    update(l , mid ,ls , a , b, v);
 58     else if( mid<a )    update(mid+1, r, rs ,a ,b , v );
 59     else{
 60         update( l ,mid , ls , a, mid,  v );
 61         update( mid+1,  r, rs, mid+1, b , v );
 62     }
 63     pushup(l ,r, idx);
 64 }
 65 
 66 void solve(){
 67     std::sort(h+1, h+M+1) ;
 68     h[0] = 0 ;
 69     __int64 res = 0 ;
 70     for(int i=1;i<=M;i++){
 71         int hh = h[i] ;
 72         int m = 0 ;
 73         for(int j=1;j<=N;j++){
 74             if( p[j].h >= hh ){
 75                 pp[m] = Seg( p[j].p1.x , p[j].p2.x ,p[j].p1.y , 1 ) ;
 76                 x[m++] = p[j].p1.x ;
 77                 pp[m] = Seg( p[j].p1.x , p[j].p2.x ,p[j].p2.y , -1 );
 78                 x[m++] = p[j].p2.x ;
 79             }
 80         }
 81         std::sort( x , x+m );
 82         std::sort(pp ,pp+m );
 83         int n = 1 ;
 84         for(int j=1;j<m;j++){
 85             if( x[j-1] != x[j] )    x[n++] = x[j] ;
 86         }
 87         n-- ;
 88         memset(col, 0, sizeof(col) );
 89         memset(sum, 0 ,sizeof(sum) );
 90         __int64 ans = 0 ;
 91 
 92         for(int j=0;j<m-1;j++){
 93             int s = find( pp[j].l, 0 ,n );
 94             int e = find( pp[j].r , 0 , n ) - 1 ;
 95             if(s <= e)  update(0, MAXN<<1 ,1 , s, e ,pp[j].s );
 96             ans += (__int64)(sum[1])*(__int64)( pp[j+1].h - pp[j].h );
 97         }
 98         res += ans*(__int64)( h[i] - h[i-1] ) ;
 99     }
100     printf("%I64d
",res);
101 }
102 
103 int main(){
104     int ncas , cas ;
105     scanf("%d",&ncas);
106     for(cas=1 ;cas<=ncas ; cas++){
107         scanf("%d %d",&N, &M );
108         for(int i=1;i<=M;i++){
109             scanf("%d",&h[i]);
110         }
111         for(int i=1;i<=N;i++){
112             p[i].p1.get() ;
113             p[i].p2.get() ;
114             int a ;
115             scanf("%d",&a);
116             p[i].h = h[a] ;
117         }
118         printf("Case %d: ",cas);
119         solve() ;
120     }
121     return 0 ;
122 }

pOj 2932 Coneology （圆的包含关系）

转载自：http://blog.csdn.net/ch2010091/article/details/7795171

给出了n个互不相交的圆。各个圆之间有可能一个完全包含了另一个。这里包含就是一个圆整个都被另一个圆圈再里面。

现在求那些没有被包含的圆的序号。没有圆存在相交关系。

分析：

因为题目内的圆不存在相交的情况，直接把储存每个圆的左端点和右端点的x坐标。然后从左扫到右，如果满足是最外面的圆，就储存在set里面。如何判断满足，就是对每一个x，如果是左端点的x坐标就来判断其对应的圆，是否是在set中储存的圆内，如果不是，就存到set中。如果是右端点的x坐标，就pop出该圆。

考虑扫描线,选择一个圆的最左点和最右点作为事件点.然后用一条竖直线从左到右扫一遍.
    维护一个数据结构,里面保存着和扫描线相交的powerful 圆.
    如果一个事件是某圆的最右点,并且该圆在数据结构中,就意味着要把这个圆删掉.
    如果一个事件是某圆的最左点,当它不被其他圆包含时,就意味着可能要把它加入到我们的数据结构中,
怎么检查它有没有被其他圆包含呢?我们的数据结构里的圆都是一些 powerful 圆,他们互不相交,也就是
说他们在当前的扫描线上占的区间也互不相交, 如果我们只是记录圆心在扫描线的投影, 把高的投影称为前,
把低的投影低称为后,那么可能与当前圆发生关系的只是它的前一个圆,后一个圆.

加入set的集合的元素是.额.是不相互包含的圆.也就是说两两关系是相离.那么一个圆只要和它上下两圆无关系，自然也不会和这之外的圆有关系了.

然后这里判断一个圆的上下，就没有那么麻烦了.按圆心位置高下来就行.即能和当前圆发生关系的就只有它上下的圆。毕竟加入set的集合的圆都是没有关系的.

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<set>
  5 #include <cmath>
  6 #include<algorithm>
  7 using namespace std;
  8 const int L=50001;
  9 const double eps=0.0;
 10 struct point
 11 {
 12     double x,y,r;
 13     int va,id;
 14 }cir[L];
 15 struct node
 16 {
 17     double x;
 18     int id,flag;
 19 }lr[L*2];
 20 set<int> seg;
 21 typedef set<int>::iterator it;
 22 bool cmp(point a,point b)
 23 {
 24     return a.y<b.y || a.y==b.y && a.x<b.x;
 25 }
 26 bool cmp1(node a,node b)
 27 {
 28     return a.x<b.x;
 29 }
 30 bool pr(point a,point b)
 31 {
 32     return a.x==b.x && a.y==b.y;
 33 }
 34 double dis(point a,point b)
 35 {
 36     a.x-=b.x;a.y-=b.y;
 37     return sqrt(a.x*a.x+a.y*a.y);
 38 }
 39 int check(point a,point b)
 40 {
 41     if(pr(a,b))
 42         if(a.r>b.r-eps) return 1;
 43     if(a.r<b.r) return 0;
 44     double d=dis(a,b);
 45     if(d<a.r-b.r-eps) return 1;
 46     return 0;
 47 }
 48 void slove(int n)
 49 {
 50     int i,j;
 51     for(i=0;i<n;i++)
 52     {
 53         if(lr[i].flag==0)
 54         {
 55             it idx=seg.insert(lr[i].id).first;
 56             it be=idx,ed=idx;
 57             if(seg.size()>=2)
 58             {
 59                 if(be==seg.begin())
 60                 {
 61                     j=*++be;
 62                    if(check(cir[j],cir[lr[i].id]))
 63                         {   
 64                             cir[lr[i].id].va=1;
 65                             seg.erase(lr[i].id);
 66                         }
 67                 }
 68                 else if(++ed==seg.end())
 69                 {
 70                     j=*--be;
 71                     if(check(cir[j],cir[lr[i].id]))
 72                         {
 73                             cir[lr[i].id].va=1;
 74                             seg.erase(lr[i].id);
 75                         }
 76                 }
 77                 else
 78                 {
 79                     ed--;
 80                     if((check(cir[*--be],cir[lr[i].id])) || (check(cir[*++ed],cir[lr[i].id])))
 81                         {
 82                             cir[lr[i].id].va=1;
 83                             seg.erase(lr[i].id);
 84                         }
 85                 }
 86             }
 87         }
 88         else
 89             seg.erase(lr[i].id);
 90     }
 91 }
 92 int ans[L];
 93 int main()
 94 {
 95     int i,j,n,m;
 96     while(~scanf("%d",&n))
 97     {
 98         j=0;
 99         for(i=0;i<n;i++)
100         {
101             scanf("%lf %lf %lf",&cir[i].r,&cir[i].x,&cir[i].y);
102             cir[i].id=i;
103             cir[i].va=0;
104         }
105         sort(cir,cir+n,cmp);
106         for(i=0;i<n;i++)
107         {
108             lr[j].id=i;lr[j].x=cir[i].x-cir[i].r;lr[j++].flag=0;
109             lr[j].id=i;lr[j].x=cir[i].x+cir[i].r;lr[j++].flag=1;
110         }
111         sort(lr,lr+j,cmp1);
112         slove(j);
113         j=0;
114         for(i=0;i<n;i++)
115             if(cir[i].va==0) ans[j++]=cir[i].id+1;
116         printf("%d
",j);
117         sort(ans,ans+j);
118         for(i=0;i<j;i++)
119             printf("%d%c",ans[i],i==j-1?'
':' ');
120     }
121     return 0;
122 }

扫描线题目汇总 （里面的题解和代码非原创）

扫描线题目汇总（里面的题解和代码非原创）