P3081 USACO13MAR Hill Walk G
题目描述
There are N hills (1 <= N <= 100,000). Each hill takes the form of a line segment from (x1, y1) to (x2, y2) where x1 < x2 and y1 < y2. None of these segments intersect or touch, even at their endpoints, and furthermore, the first hill satisfies (x1, y1) = (0,0).
Bessie the cow starts at (0,0) on the first hill. Whenever Bessie is on a hill, she climbs up until she reaches the end. Then she jumps off the edge. If she lands on another hill, she continues walking on that hill; otherwise, she falls very far until she lands safely on a cushion of pillows at y = -infinity. Each hill (x1, y1) -> (x2, y2) should be regarded as containing the point (x1, y1) but not containing the point (x2, y2), so that Bessie will land on the hill if she falls on it from above at a position with x = x1, but she will not land on the hill if she falls on it from above at x = x2.
Please count the total number of hills that Bessie touches at some point during her walk.
有 \(N(1 \le N \le 10 ^ 5)\)座小山，每座山所占的区域用直线 \((x1, y1)\) 到 \((x2, y2)\) 来表示（\(x1 < x2\) 并且 \(y1 < y2\)）。也就是说这些山用笛卡尔坐标系里的线段来表示，这些用于表示小山的线段都没有任何交点，第一座山的一端位于 \((x1, y1) = (0,0)\)。
贝西从 \((0,0)\) 开始在第一座山上漫步，一旦贝西到了一座山，她会一直走到该山的终点，这时，她会从边缘处起跳，如果她降落到另一座山上，她会继续在新的山上漫步。贝西起跳后沿 \(y\) 轴方向下落，如果贝西不能降落到一座山上，她会一直下落，直到到达 \(y\) 轴的负无穷大位置（\(y = -\infin\)）。
每座用线段表示的山 \((x1, y1) \to (x2, y2)\) 包含 \((x1, y1)\) 这个点，但不包含 \((x2, y2)\)，请计算出贝西总共在多少座山上漫步了。
输入格式
* Line 1: The number of hills, N.
* Lines 2..1+N: Line i+1 contains four integers (x1,y1,x2,y2)
describing hill i. Each integer is in the range
0..1,000,000,000.
输出格式
* Line 1: The number of hills Bessie touches on her journey.
输入输出样例 #1
输入 #1
4
0 0 5 6
1 0 2 1
7 2 8 5
3 0 7 7
输出 #1
3
说明/提示
There are four hills. The first hill runs from (0,0) to (5,6), and so on.
Bessie walks on hills #1, #4, and finally #3.
解题报告
扫描线+平衡树。
具体的，用扫描线维护线段的横坐标，用平衡树维护线段之间的高度。
首先将每个线段拆成起点和终点，按横坐标升序排序后扫描。
扫到了某个线段的起点就插进平衡树中。
扫到了某个线段的终点，如果这个线段是当前线段，那么用平衡树找到该线段下方的第一条线段作为新的当前线段，并把之前的当前线段从平衡树中删除；如果不是当前线段，就直接从删除平衡树中删除。
那么就剩下一个问题：怎么比较两个线段的上下关系？
其实我自己没推明白，这里引一个图解，是Soh_paramEEMS 的 题解：P3081 USACO13MAR Hill Walk G。
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1001100;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int n;struct seg
{int xl,yl,xr,yr,pos;inline void putin(int p){xl=read(),yl=read();xr=read(),yr=read();pos=p;}bool operator < (const seg &t)const{if(xr<t.xr)return 1LL*(t.xr-xr)*(t.yr-t.yl)<1LL*(t.xr-t.xl)*(t.yr-yr);elsereturn 1LL*(xr-t.xr)*(yr-yl)>1LL*(xr-xl)*(yr-t.yr);}}s[N];struct dot
{int x,y,pos;bool operator < (const dot &t)const{ return x<t.x || ( x==t.x && y<t.y ); }
}p[N];
int nP;set<seg> T;
set<seg>::iterator it1;
set<seg>::iterator it2;signed main()
{n=read();for(int i=1;i<=n;i++){s[i].putin(i);p[++nP]=(dot){ s[i].xl,s[i].yl,i };p[++nP]=(dot){ s[i].xr,s[i].yr,i };}sort(p+1,p+nP+1);T.insert(s[1]);int pos=1,tot=1;for(int i=2;i<=nP;i++){dot u=p[i];seg tmp=s[u.pos];if(u.x==tmp.xl) T.insert(tmp);else if(u.pos==pos){it1=T.find(tmp);if(it1==T.begin()) break;it2=it1;--it2;pos=it2->pos;T.erase(it1);tot++;}else T.erase(tmp);}printf("%d\n",tot);return 0;
}